class Solution {
public:
string mergeAlternately(string word1, string word2) {
int len1 = word1.length();
int len2 = word2.length();
string ans;
for (int i = 0, j = 0, k = 0; i < word1.length() + word2.length(); i++) {
if (i % 2 == 0 && j < len1 || k == len2) {
ans += word1[j];
j++;
}
if (i % 2 == 1 && k < len2 || j == len1) {
ans += word2[k];
k++;
}
}
return ans;
}
};
我检查了是否附加空字符,但它小于 Len,所以我不知道代码有什么问题。
程序的逻辑要求在循环的每次迭代中仅将一个字符附加到变量
ans
。这是因为变量 i
每次迭代仅增加一次。
这会在
len1 <= len2
时导致问题。将 word1
的最后一个字符附加到 ans
后,变量 j
会递增,使其等于 len1
。当执行以下 if 语句时,它发现 j == len1
,因此它将第二个字符附加到 ans
(来自 word2
)。这意味着在同一迭代中已将两个字符添加到 ans
,但是 i
仅递增一次。
这会产生一个“off-by-one”错误,导致循环执行次数过多。在最后一次迭代期间,当使用超出范围的下标对 word1
进行索引时,您将进入“未定义行为”领域。发生这种情况是因为k == len2
。
if (i % 2 == 0 && j < len1 || k == len2) {
ans += word1[j]; // UB - subscript j == len1
j++; // now j == len1 + 1
}
对于 UB,所有的赌注都被关闭,但可能是小字符串优化用空字符(
'\0'
)填充了字符串缓冲区,因此这是访问 word1[len1]
时选择的字符。
j
设置为len + 1
。因此,
word2
的 if 语句不会尝试添加另一个字符。if (i % 2 == 1 && k < len2 || j == len1) {
ans += word2[k];
k++;
}
一个简单的修复
@Unmitigated 在评论中提供了一个简单的修复:在测试
word2
ans
。
if (i % 2 == 0 && j < len1 || k == len2) {
ans += word1[j];
j++;
}
else if (i % 2 == 1 && k < len2 || j == len1) {
ans += word2[k];
k++;
}
完整的程序
以下程序包含一个运行 LeetCode 网站上的所有三个示例的驱动程序。
// main.cpp
#include <iostream>
#include <iomanip>
#include <string>
// This using declaration allows the LeetCode Solution
// to be used without modifying its function signature.
using std::string;
class Solution {
public:
string mergeAlternately(string word1, string word2) {
int len1 = word1.length();
int len2 = word2.length();
string ans;
for (int i = 0, j = 0, k = 0; i < word1.length() + word2.length(); i++) {
if (i % 2 == 0 && j < len1 || k == len2) {
ans += word1[j];
j++;
}
else if (i % 2 == 1 && k < len2 || j == len1) {
ans += word2[k];
k++;
}
}
return ans;
}
};
void solve(
std::string_view heading,
std::string const& word1,
std::string const& word2)
{
std::string ans{ Solution{}.mergeAlternately(word1, word2) };
std::cout
<< std::boolalpha
<< heading
<< "\n"
<< "\n Input: word1 = " << std::quoted(word1)
<< ", word2 = " << std::quoted(word2)
<< "\n Output: " << std::quoted(ans) << ", length = " << ans.length()
<< "\n\n";
}
int main()
{
std::cout << "LeetCode 1768. Merge Strings Alternately"
"\nhttps://leetcode.com/problems/merge-strings-alternately/description/"
"\n\n";
solve("Example 1", "abc", "pqr");
solve("Example 2", "ab", "pqrs");
solve("Example 3", "abcd", "pq");
}
// end file: main.cpp
输出
LeetCode 1768. Merge Strings Alternately
https://leetcode.com/problems/merge-strings-alternately/description/
Example 1
Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr", length = 6
Example 2
Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs", length = 6
Example 3
Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd", length = 6
下面的解决方案在循环的每次迭代中向答案添加两个字符。当
word1
word2
耗尽时,它会停止。
退出循环后,将测试i
和j
以确定是否分别在
word1
或word2
中保留任何字符。剩下的内容都会使用子字符串附加到单个“块”中的答案中。因为它始终使用类型 std::string::size_type
,并且不与 int
混合,所以编译时不会出现任何警告。
class Solution
{
public:
string mergeAlternately(string word1, string word2) {
auto const len1 = word1.length(); // Here, auto == std::string::size_type
auto const len2 = word2.length();
string ans;
ans.reserve(len1 + len2); // avoid reallocations as `ans` grows.
// Use correct type
std::string::size_type i{}; // index into `word1`
std::string::size_type j{}; // index into `word2`
// while "both strings have characters remaining"
while (i < len1 && j < len2) {
ans.push_back(word1[i++]);
ans.push_back(word2[j++]);
}
// append whatever remains
if (i < len1)
ans += word1.substr(i);
else if (j < len2)
ans += word2.substr(j);
return ans;
}
};