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

问题描述 投票:0回答:1

enter image description here

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

c++ string merge
1个回答
0
投票

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

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

© www.soinside.com 2019 - 2024. All rights reserved.