Leetcode 复健1: 1768

之前面一个中小厂不太顺利，回过头来发现我 vibe coding 太多导致基本的数据结构已经还给院长了，自己手写一个费劲的很，打算从 easy 难度的恢复一下，重走长征路

1768. 交替合并字符串

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

示例 1：

输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：

输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：

输入：word1 = "abcd", word2 = "pq"
输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d

提示：

• 1 <= word1.length, word2.length <= 100
• word1 和 word2 由小写英文字母组成

最开始的思路是既然是交替，那就直接交替 insert，最后看哪个长就把剩下的插进去就行，脑淤血代码如下：

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = word1;
        for(int i=0;i<word1.size();i++)if(i<word2.size())ans.insert(i*2+1,1,word2[i]);
        if(word2.size()>word1.size())ans.append(word2.substr(word1.size(),word2.size()-word1.size()));
        return ans;
    }
};

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        string ans = word1;
        for(int i=0;i<word1.size();i++)if(i<word2.size())ans.insert(i*2+1,1,word2[i]);
        if(word2.size()>word1.size())ans.append(word2.substr(word1.size(),word2.size()-word1.size()));
        return ans;
    }
};

提交上去，嘛，虽然AC了，但是不尽如人意：

说实话，这个时间复杂度初看以为是 O(N) ，后来思考了一下 insert 的问题发现不对劲。在 C++ 中，std::string::insert 在中间插入字符是一个 O(L) 的操作（L 是当前字符串的长度），因为插入点后面的所有字符都必须在内存里往后挪动一位。因此，这个脑淤血的循环部分的总体复杂度高达：O(M \times (M + N)) = O(M^2 + MN)

其实改成双指针就好很多了

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int m=word1.size(),n=word2.size();
        int i=0,j=0;
        string ans;
        while(i<m || j<n){
            if(i<m){
                ans.push_back(word1[i]);
                i++;
            }
            if(j<n){
                ans.push_back(word2[j]);
                j++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int m=word1.size(),n=word2.size();
        int i=0,j=0;
        string ans;
        while(i<m || j<n){
            if(i<m){
                ans.push_back(word1[i]);
                i++;
            }
            if(j<n){
                ans.push_back(word2[j]);
                j++;
            }
        }
        return ans;
    }
};