LeetCode 1768简单双指针/字符串
交替合并字符串 图解题解
这道题到底在问什么
给定 word1 和 word2,从 word1 第 0 位、word2 第 0 位起交替取字符拼接;较短的串取完后,把较长串的剩余字符直接追加到末尾,返回合并结果。
- 输入
- word1="abc", word2="pqr"
- 输出
- "apbqcr"(等长,完全交替)
- 输入
- word1="ab", word2="pqrs"
- 输出
- "apbqrs"(word2 剩 rs 追加)
最优解：一步一步想明白
- 3记住「同一个 i,先尝试取 word1[i]、再尝试取 word2[i],越界就跳过」,下面每一帧都在套它。
- 4轮到 word1 的第 0 位字符 "a"。先尝试取 word1[0],它在 word1 长度内,可以取。
- 5"a" 接到结果末尾(第 0 位,绿色)。
- 6轮到 word2 的第 0 位字符 "p"。同一轮里再尝试取 word2[0],它在 word2 长度内,可以取。
- 7"p" 接到结果末尾(第 1 位,绿色)。这一轮 word1、word2 都取过了,进入下一轮。
- 8轮到 word1 的第 1 位字符 "b"。先尝试取 word1[1],它在 word1 长度内,可以取。
- 9"b" 接到结果末尾(第 2 位,绿色)。
- 10轮到 word2 的第 1 位字符 "q"。同一轮里再尝试取 word2[1],它在 word2 长度内,可以取。
- 11"q" 接到结果末尾(第 3 位,绿色)。这一轮 word1、word2 都取过了,进入下一轮。
- 12轮到 word1 的第 2 位字符 "c"。先尝试取 word1[2],它在 word1 长度内,可以取。
- 13"c" 接到结果末尾(第 4 位,绿色)。
- 14轮到 word2 的第 2 位字符 "r"。同一轮里再尝试取 word2[2],它在 word2 长度内,可以取。
- 15"r" 接到结果末尾(第 5 位,绿色)。这一轮 word1、word2 都取过了,进入下一轮。
- 16轮到 word1 的第 3 位字符 "d"。先尝试取 word1[3],它在 word1 长度内,可以取。
- 17"d" 接到结果末尾(第 6 位,绿色)。
- 18注意:i = 3 已经等于 word2 的长度 3,不满足 i < 3,所以 word2 这一支跳过,只剩 word1 在取。从刚接上的 "d" 开始,word1 剩下的字符一个接一个补到末尾,后面还会继续接 "ef"。
- 19轮到 word1 的第 4 位字符 "e"。先尝试取 word1[4],它在 word1 长度内,可以取。
- 20"e" 接到结果末尾(第 7 位,绿色)。
- 21轮到 word1 的第 5 位字符 "f"。先尝试取 word1[5],它在 word1 长度内,可以取。
- 22"f" 接到结果末尾(第 8 位,绿色)。
- 23合并完成,结果是 "apbqcrdef",和开头说的一致。回头看:同一个 i 先取 word1[i]、再取 word2[i],越界就跳过;word2 用完后,word1 的 "def" 自然一路接到末尾。一遍扫完,时间 O(n+m)。
⚠️ 容易写错的地方
✗ 错：只循环到较短串的长度
✓ 对：循环到 max(len1, len2)
只到短串长度会漏掉长串剩余的字符,合不全
✗ 错：不判越界直接取 word1[i]、word2[i]
✓ 对：每次取前先判 i < 该串长度
短串用完后再按 i 取会越界报错
✗ 错：取完一串再取另一串(非交替)
✓ 对：同一个 i 先 word1[i] 再 word2[i]
题目要的是逐字符交替,不是先接完一个再接另一个
完整代码（Python / C++ / Java）
Python
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
ans = []
for i in range(max(len(word1), len(word2))):
if i < len(word1):
ans.append(word1[i])
if i < len(word2):
ans.append(word2[i])
return ''.join(ans)C++
#include <string>
using namespace std;
class Solution {
public:
string mergeAlternately(string word1, string word2) {
string ans;
int n = max(word1.size(), word2.size());
for (int i = 0; i < n; ++i) {
if (i < (int)word1.size()) ans += word1[i];
if (i < (int)word2.size()) ans += word2[i];
}
return ans;
}
};Java
import java.util.*;
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int n = Math.max(word1.length(), word2.length());
for (int i = 0; i < n; i++) {
if (i < word1.length()) sb.append(word1.charAt(i));
if (i < word2.length()) sb.append(word2.charAt(i));
}
return sb.toString();
}
}复杂度
时间
O(n+m)
n、m 是两串长度,每个字符恰好被取一次、接一次
空间
O(n+m)
结果串本身要装下两串全部字符;Java/C++ 用可变缓冲,不算额外开销
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 交替合并字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题和「合并两个有序数组/链表」有什么异同?+
相同点是都用「交替/并行推进」的指针思路把两段拼成一段。不同点是本题是无条件按位置交替、不比较大小,而合并有序序列要比较当前两个元素谁小才取谁。本题更简单,固定按下标交替即可。
能不能用双指针 i、j 分别指 word1、word2 来写?+
可以。i、j 各从 0 开始,轮流取 word1[i++]、word2[j++],谁先到头就把另一个剩余整段接上。和按单个 i 判越界本质一样,只是把「同一个 i」拆成两个独立下标,逻辑等价。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 交替合并字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。