交错字符串 图解题解
这道题到底在问什么
- 输入
- s1="aabcc", s2="dbbca", s3="aadbbcbcac"
- 输出
- true
最优解：为什么这么做
一句话答案：LeetCode 97 交错字符串：判 s3 能否由 s1、s2 各自保序交错拼成。二维 DP，dp[i][j] 记 s1 前 i、s2 前 j 位能否交错成 s3 前 i+j 位，看上、左两条来路。时间 O(m·n)、空间 O(n)。
从 s1、s2 轮流取，能拼出 s3 吗
给 s1、s2、s3 三根字符串，问能不能从 s1、s2 里轮流取字符、各自顺序不打乱，正好拼出 s3。题面例子 s1="aabcc"、s2="dbbca"、s3="aadbbcbcac"，答案 true。要判的是能不能拼成，不是给出某种拼法。
为什么贪心逐位配会漏解
贪心最顺手：拿 s3 当前字符比 s1、s2 的待取首字符，对上谁取谁。两边都能对上时，随手选一个可能选中死路，贪心不回头就把本能拼成的判成拼不成。枚举所有取法又指数爆炸、前缀反复重算。把两串各取几个记成状态存下来复用，就从指数（慢到爆）压回多项式（能接受）。
状态为什么定成二维 dp[i][j]
定义 dp[i][j] 表示「s1 前 i 个、s2 前 j 个字符，能不能交错拼出 s3 的前 i+j 个字符」。为什么盯 s3 前 i+j 位？从 s1 取 i 个、s2 取 j 个，共取出 i+j 个字符，正好是 s3 开头 i+j 个：取多少就对应开头多少位。所以要对上 s3 第 i+j 位，下标从 0 数即 s3[i+j-1]。dp[0][0] 各取 0 个拼出空串，天然成立。
每格为什么只看上格和左格
填 dp[i][j] 时，s3 第 i+j 位只可能来自两处：s1 取的 s1[i-1]，或 s2 取的 s2[j-1]。走前者，要 s1[i-1]==s3[i+j-1] 且前面拼得成，那是上格 dp[i-1][j]；走后者，要 s2[j-1]==s3[i+j-1] 且左格 dp[i][j-1] 成立。通一条就成：dp[i][j] =（dp[i-1][j] 且 s1[i-1]==s3[i+j-1]）或（dp[i][j-1] 且 s2[j-1]==s3[i+j-1]）。
拿题面示例逐格算几步
s1="aabcc"、s2="dbbca"、s3="aadbbcbcac"，建 6×6 表。dp[0][0]=能。dp[1][0] 走上格，s1[0]='a' 对 s3[0]='a' 对上、dp[0][0]=能，得能。dp[0][1] 走左格，s2[0]='d' 对 s3[0]='a' 对不上，得不能；第一行其余全不能。dp[2][1]：i+j 为 3，对 s3[2]='d'，上格 s1[1]='a'≠'d' 断、左格 s2[0]='d'=='d' 且 dp[2][0]=能，得能。填到右下角 dp[5][5]：i+j 为 10，对 s3[9]='c'，上格 s1[4]='c'=='c' 且 dp[4][5]=能，得能，答案 true。
为什么先判长度、下标要用 i+j-1
表有 (m+1)×(n+1) 格，每格常数比较，时间 O(m·n)；每格只用上格和左格，逐行滚动（滚动数组=只留最近一行、循环覆盖旧值）空间可压到 O(n)。两个边界最易踩。一是开头先判 m+n 是否等于 len(s3)：长度对不上就拼不成 s3，直接返回 false；漏了这步 s3[i+j-1] 还会越界。二是 s3 下标用 i+j-1：当前位下标 i+j-1，写错全表算错。
▶ 动画逐步走查（共 73 步）——想跟着动画一帧帧对照就展开
- 3记住这一句：每填一格，只看两条路——这一步要么从 s1 取一个字符，要么从 s2 取一个字符，看谁能对上 s3 当前位。
- 4左上角先点亮 ✓：s1、s2 各取 0 个字符，拼出的就是空串，当然成立。其余格从这里逐格推。
- 5这一格只能走「左」这一条路：从 s2 取 'd' 去对 s3 第 1 位 'a'，对不上，还要看左格是否成立。
- 6落子：dp[0][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 1 位。
- 7这一格只能走「左」这一条路：从 s2 取 'b' 去对 s3 第 2 位 'a'，对不上，还要看左格是否成立。
- 8落子：dp[0][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 2 位。
- 9这一格只能走「左」这一条路：从 s2 取 'b' 去对 s3 第 3 位 'd'，对不上，还要看左格是否成立。
- 10落子：dp[0][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
- 11这一格只能走「左」这一条路：从 s2 取 'c' 去对 s3 第 4 位 'b'，对不上，还要看左格是否成立。
- 12落子：dp[0][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
- 13这一格只能走「左」这一条路：从 s2 取 'a' 去对 s3 第 5 位 'b'，对不上，还要看左格是否成立。
- 14落子：dp[0][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
- 15这一格只能走「上」这一条路：从 s1 取 'a' 去对 s3 第 1 位 'a'，对上了，还要看上格是否成立。
- 16落子：dp[1][0] = ✓。有一条路走通了——前 1 个字符可以交错拼出。
- 17判 dp[1][1]：s3 第 2 位是 'a'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
- 18落子：dp[1][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 2 位。
- 19判 dp[1][2]：s3 第 3 位是 'd'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'd' 且来路成立，这格就 ✓。
- 20落子：dp[1][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
- 21判 dp[1][3]：s3 第 4 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 22落子：dp[1][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
- 23判 dp[1][4]：s3 第 5 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 24落子：dp[1][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
- 25判 dp[1][5]：s3 第 6 位是 'c'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 26落子：dp[1][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
- 27这一格只能走「上」这一条路：从 s1 取 'a' 去对 s3 第 2 位 'a'，对上了，还要看上格是否成立。
- 28落子：dp[2][0] = ✓。有一条路走通了——前 2 个字符可以交错拼出。
- 29判 dp[2][1]：s3 第 3 位是 'd'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'd' 且来路成立，这格就 ✓。
- 30落子：dp[2][1] = ✓。有一条路走通了——前 3 个字符可以交错拼出。
- 31判 dp[2][2]：s3 第 4 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 32落子：dp[2][2] = ✓。有一条路走通了——前 4 个字符可以交错拼出。
- 33判 dp[2][3]：s3 第 5 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 34落子：dp[2][3] = ✓。有一条路走通了——前 5 个字符可以交错拼出。
- 35判 dp[2][4]：s3 第 6 位是 'c'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 36落子：dp[2][4] = ✓。有一条路走通了——前 6 个字符可以交错拼出。
- 37判 dp[2][5]：s3 第 7 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 38落子：dp[2][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 7 位。
- 39这一格只能走「上」这一条路：从 s1 取 'b' 去对 s3 第 3 位 'd'，对不上，还要看上格是否成立。
- 40落子：dp[3][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
- 41判 dp[3][1]：s3 第 4 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 42落子：dp[3][1] = ✓。有一条路走通了——前 4 个字符可以交错拼出。
- 43判 dp[3][2]：s3 第 5 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 44落子：dp[3][2] = ✓。有一条路走通了——前 5 个字符可以交错拼出。
- 45判 dp[3][3]：s3 第 6 位是 'c'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 46落子：dp[3][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
- 47判 dp[3][4]：s3 第 7 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 48落子：dp[3][4] = ✓。有一条路走通了——前 7 个字符可以交错拼出。
- 49判 dp[3][5]：s3 第 8 位是 'c'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 50落子：dp[3][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 8 位。
- 51这一格只能走「上」这一条路：从 s1 取 'c' 去对 s3 第 4 位 'b'，对不上，还要看上格是否成立。
- 52落子：dp[4][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
- 53判 dp[4][1]：s3 第 5 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 54落子：dp[4][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
- 55判 dp[4][2]：s3 第 6 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 56落子：dp[4][2] = ✓。有一条路走通了——前 6 个字符可以交错拼出。
- 57判 dp[4][3]：s3 第 7 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 58落子：dp[4][3] = ✓。有一条路走通了——前 7 个字符可以交错拼出。
- 59判 dp[4][4]：s3 第 8 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 60落子：dp[4][4] = ✓。有一条路走通了——前 8 个字符可以交错拼出。
- 61判 dp[4][5]：s3 第 9 位是 'a'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
- 62落子：dp[4][5] = ✓。有一条路走通了——前 9 个字符可以交错拼出。
- 63这一格只能走「上」这一条路：从 s1 取 'c' 去对 s3 第 5 位 'b'，对不上，还要看上格是否成立。
- 64落子：dp[5][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
- 65判 dp[5][1]：s3 第 6 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 66落子：dp[5][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
- 67判 dp[5][2]：s3 第 7 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
- 68落子：dp[5][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 7 位。
- 69判 dp[5][3]：s3 第 8 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 70落子：dp[5][3] = ✓。有一条路走通了——前 8 个字符可以交错拼出。
- 71判 dp[5][4]：s3 第 9 位是 'a'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
- 72落子：dp[5][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 9 位。
- 73判 dp[5][5]：s3 第 10 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
- 74落子：dp[5][5] = ✓。有一条路走通了——前 10 个字符可以交错拼出。
- 75右下角 dp[5][5] = ✓：用完 s1、s2 的全部字符，正好交错拼出整个 s3，所以答案是 true。
⚠️ 容易写错的地方
✗ 错：不先判 m+n != len(s3)
✓ 对：长度对不上直接 false
长度不等时根本不可能交错拼成
✗ 错：用贪心逐位匹配
✓ 对：必须二维 DP 记忆
某位字符 s1、s2 都能匹配时，贪心选错会漏掉可行解
✗ 错：比错 s3 的下标
✓ 对：s3 当前位是第 i+j 位（s3[i+j-1]）
已取的总字符数 = i+j，错位会全盘算错
完整代码（Python / C++ / Java）
Python
def isInterleave(s1, s2, s3):
m, n = len(s1), len(s2)
if m + n != len(s3): return False
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True
for i in range(m+1):
for j in range(n+1):
if i and s1[i-1]==s3[i+j-1]:
dp[i][j] |= dp[i-1][j]
if j and s2[j-1]==s3[i+j-1]:
dp[i][j] |= dp[i][j-1]
return dp[m][n]C++
bool isInterleave(string s1, string s2, string s3){
int m = s1.size(), n = s2.size();
if (m + n != (int)s3.size()) return false;
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++) {
if (i && s1[i-1]==s3[i+j-1]) dp[i][j] = dp[i][j] || dp[i-1][j];
if (j && s2[j-1]==s3[i+j-1]) dp[i][j] = dp[i][j] || dp[i][j-1];
}
return dp[m][n];
}Java
boolean isInterleave(String s1, String s2, String s3){
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++)
for (int j = 0; j <= n; j++) {
if (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1))
dp[i][j] = dp[i][j] || dp[i-1][j];
if (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1))
dp[i][j] = dp[i][j] || dp[i][j-1];
}
return dp[m][n];复杂度
时间
O(m·n)
每格 O(1)，共 (m+1)×(n+1) 格
空间
O(m·n)
整表；每格只依赖上格/左格，可滚动到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 交错字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么能把空间从 O(m·n) 压到 O(n)？+
dp[i][j] 只依赖同列上一行的 dp[i-1][j] 和同行左边的 dp[i][j-1]，更早的行再也用不到。所以按行从上往下填时只留一行：填新行第 j 格时，数组里第 j 格还是旧值（正好是上格 dp[i-1][j]），第 j-1 格已被本行刷新（正好是左格 dp[i][j-1]），两条来路都读得到。一行 n+1 长就够，空间降到 O(n)，时间仍是 O(m·n)。
能用 DFS 加记忆化做吗？+
能，而且和这张表等价。把 (i,j) 看成网格上的点，从 (0,0) 出发，每步按 s1[i-1] 或 s2[j-1] 是否对上 s3[i+j-1]，决定能不能往下走一格（取 s1）或往右走一格（取 s2），目标是走到 (m,n)。为避免同一个 (i,j) 被反复搜，把算过的结果记进备忘表，复杂度同样 O(m·n)。
为什么贪心逐位匹配是错的，能举个例子吗？+
当 s3 当前位在 s1、s2 的待取首字符里都能对上时，贪心随手选一个，可能选到那条走不通的岔路。比如两边都能提供 'a'，选了 s1 的 'a' 后面卡死，其实该选 s2 的 'a' 才拼得成——贪心不回头就把可行解判没了。二维 DP 把「s1 取 i 个、s2 取 j 个」每种组合都记下来，不会因为某一步选错而漏掉解。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 交错字符串 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。