其他系列文章导航
文章目录
前言
这是力扣的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 <= 100word1和word2由小写英文字母组成
二、题解
2.1方法一：双指针
思路与算法：
我们直接按照题目的要求模拟即可。我们使用两个指针 i 和 j，初始时分别指向两个字符串的首个位置。随后的每次循环中，依次进行如下的两步操作：
- 如果 i 没有超出 word1的范围，就将 word1加入答案，并且将 i 移动一个位置。
- 如果 j 没有超出 word2的范围，就将 word2 加入答案，并且将 j 移动一个位置。
当 i 和 j 都超出对应的范围后，结束循环并返回答案即可。
2.2方法二：循环拼接
思路与算法：
我们直接按照题目的要求模拟即可。我们先求出两个字符串最长的长度和最短的长度，按照最短长度将两个字符串进行交替合并，再交替拼接最后多余的部分。
- 当两个字符串长度不等时，需要交替拼接最后多余的部分。
- 如果相等，则直接交替拼接。
三、代码
3.1方法一：双指针
Java版本：
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版本：
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版本：
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++版本：
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)。注意这里不计入返回值需要的空间。
