我的 leetcode 1768 中的 Merge String Alternately 函数有什么问题

Question

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，所以我不知道代码有什么问题。

Answer 1

程序的逻辑要求在循环的每次迭代中仅将一个字符附加到变量

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

时使用 else-if。通过这一更改，每次迭代时只会将一个字符附加到

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;
    }
};