【LC75】No1768. 交替合并字符串

题目描述

给你两个字符串 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

链接

思路

两个字符串按单个字母交替合并，最后把较长的字符串剩下的部分，追加到合并之后字符串的末尾。

非常简洁明了的题目，但要注意不要陷在一定要判断出 word1 长还是 word2 长的迷雾中。

PS：字符串长度变化问题，使用 StringBuilder 更省空间。

解法一：双指针法

字符串一长一短，初思考很容易陷在单指针完成的欲望中。但其实看到两个字符串，双指针是应该想到的很简单的办法。

两个指针分别指向 word1 和 word2 ，如果不拘泥于较长的字符串一定要通过裁剪，直接将所有剩余部分一次性追加到答案末尾的话，在单次循环中，分别判断两个指针是否移动到字符串末尾即可。

代码

class Solution {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        int len1 = word1.length(), len2 = word2.length();
        while (i < len1 || j < len2){
            if (i < len1){
                sb.append(word1.charAt(i++));
            }
            if (j < len2){
                sb.append(word2.charAt(j++));
            }
        }
        return sb.toString();
    }
}

• 时间复杂度：O(max(len1, len2)) ，只需要遍历较长的字符串长度即可

• 空间复杂度：O(len1 + len2)

解法二：单指针法

既然两个指针每次移动的间隔相同，那么使用单指针也可以完成。此时，需要按照较短字符串的长度进行循环。

以及，较长的字符串剩余部分没必要字符一个一个循环添加，使用 substring() 可以优化成直接追加。但 substring() 也可能会创建新的字符串，从而导致额外的内存开销。

代码

class Solution {
    public String mergeAlternately(String word1, String word2) {
        StringBuilder sb = new StringBuilder();
        int minLen = Math.min(word1.length(), word2.length());
        int i = 0;
        while (i < minLen){
            sb.append(word1.charAt(i)).append(word2.charAt(i));
            i++;
        }
        sb.append(word1.substring(minLen));
        sb.append(word2.substring(minLen));       
        return sb.toString();
    }
}

• 时间复杂度：O(len1 + len2)，O(minLen) 和 两个substring() 的 复杂度 O(len1 − minLen) + O(len2 − minLen)

• 空间复杂度：O(len1 + len2)