前言
这是力扣的1768题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的两种。
一、题目描述
给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
返回 合并后的字符串 。
示例 1：
代码语言：javascript复制输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1： a b c
word2： p q r
合并后： a p b q c r示例 2：
代码语言：javascript复制
输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1： a b
word2： p q r s
合并后： a p b q r s示例 3：
代码语言：javascript复制
输入：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 <= 100word1和word2由小写英文字母组成
二、题解
2.1方法一：双指针
思路与算法：
我们直接按照题目的要求模拟即可。我们使用两个指针 i 和 j，初始时分别指向两个字符串的首个位置。随后的每次循环中，依次进行如下的两步操作：
- 如果 i 没有超出 word1的范围，就将 word1加入答案，并且将 i 移动一个位置。
- 如果 j 没有超出 word2的范围，就将 word2 加入答案，并且将 j 移动一个位置。
当 i 和 j 都超出对应的范围后，结束循环并返回答案即可。
2.2方法二：循环拼接
思路与算法：
我们直接按照题目的要求模拟即可。我们先求出两个字符串最长的长度和最短的长度，按照最短长度将两个字符串进行交替合并，再交替拼接最后多余的部分。
- 当两个字符串长度不等时，需要交替拼接最后多余的部分。
- 如果相等，则直接交替拼接。
三、代码
3.1方法一：双指针
Java版本：
代码语言：javascript复制class Solution {
public String mergeAlternately(String s1, String s2) {
int n = s1.length(), m = s2.length(), i = 0, j = 0;
StringBuilder sb = new StringBuilder();
while (i < n || j < m) {
if (i < n) sb.append(s1.charAt(i ));
if (j < m) sb.append(s2.charAt(j ));
}
return sb.toString();
}
}Python3版本：
代码语言：javascript复制class Solution:
def mergeAlternately(self, s1: str, s2: str) -> str:
n, m, i, j = len(s1), len(s2), 0, 0
ans = ""
while i < n or j < m:
if i < n:
ans = s1[i]
i = 1
if j < m:
ans = s2[j]
j = 1
return ans 3.2方法二：循环拼接
Java版本：
代码语言：javascript复制class Solution {
public String mergeAlternately(String word1, String word2) {
int n1 = word1.length(), n2 = word2.length();
int min = Math.min(n1, n2), max = Math.max(n1, n2);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < min; i ) {
sb.append(word1.charAt(i));
sb.append(word2.charAt(i));
}
if (n1 != n2) {
for (int i = min; i < max; i ) {
if (n1 > n2) {
sb.append(word1.charAt(i));
} else {
sb.append(word2.charAt(i));
}
}
}
return sb.toString();
}
}C 版本：
代码语言：javascript复制class Solution {
public:
string mergeAlternately(string word1, string word2) {
int n1 = word1.length(), n2 = word2.length();
int min = min(n1, n2), max = max(n1, n2);
vector<char> sb(min max);
for (int i = 0; i < min; i ) {
sb[i] = word1[i];
sb[i min] = word2[i];
}
if (n1 != n2) {
for (int i = min; i < max; i ) {
if (n1 > n2) {
sb[i min] = word1[i];
} else {
sb[i min] = word2[i];
}
}
}
return string(sb.begin(), sb.end());
}
};四、复杂度分析
时间复杂度：O(m n)，其中 m 和 n 分别是字符串 word1和 word2的长度。
空间复杂度：O(1) 或 O(m n)。如果使用的语言支持可修改的字符串，那么空间复杂度为 O(1)，否则为 O(m n)。注意这里不计入返回值需要的空间。
