题目描述
思路解析
一句话答案：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，写错全表算错。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句：每填一格，只看两条路——这一步要么从 s1 取一个字符，要么从 s2 取一个字符，看谁能对上 s3 当前位。
左上角先点亮 ✓：s1、s2 各取 0 个字符，拼出的就是空串，当然成立。其余格从这里逐格推。
这一格只能走「左」这一条路：从 s2 取 'd' 去对 s3 第 1 位 'a'，对不上，还要看左格是否成立。
落子：dp[0][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 1 位。
这一格只能走「左」这一条路：从 s2 取 'b' 去对 s3 第 2 位 'a'，对不上，还要看左格是否成立。
落子：dp[0][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 2 位。
这一格只能走「左」这一条路：从 s2 取 'b' 去对 s3 第 3 位 'd'，对不上，还要看左格是否成立。
落子：dp[0][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
这一格只能走「左」这一条路：从 s2 取 'c' 去对 s3 第 4 位 'b'，对不上，还要看左格是否成立。
落子：dp[0][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
这一格只能走「左」这一条路：从 s2 取 'a' 去对 s3 第 5 位 'b'，对不上，还要看左格是否成立。
落子：dp[0][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
这一格只能走「上」这一条路：从 s1 取 'a' 去对 s3 第 1 位 'a'，对上了，还要看上格是否成立。
落子：dp[1][0] = ✓。有一条路走通了——前 1 个字符可以交错拼出。
判 dp[1][1]：s3 第 2 位是 'a'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
落子：dp[1][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 2 位。
判 dp[1][2]：s3 第 3 位是 'd'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'd' 且来路成立，这格就 ✓。
落子：dp[1][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
判 dp[1][3]：s3 第 4 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[1][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
判 dp[1][4]：s3 第 5 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[1][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
判 dp[1][5]：s3 第 6 位是 'c'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[1][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
这一格只能走「上」这一条路：从 s1 取 'a' 去对 s3 第 2 位 'a'，对上了，还要看上格是否成立。
落子：dp[2][0] = ✓。有一条路走通了——前 2 个字符可以交错拼出。
判 dp[2][1]：s3 第 3 位是 'd'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'd' 且来路成立，这格就 ✓。
落子：dp[2][1] = ✓。有一条路走通了——前 3 个字符可以交错拼出。
判 dp[2][2]：s3 第 4 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[2][2] = ✓。有一条路走通了——前 4 个字符可以交错拼出。
判 dp[2][3]：s3 第 5 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[2][3] = ✓。有一条路走通了——前 5 个字符可以交错拼出。
判 dp[2][4]：s3 第 6 位是 'c'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[2][4] = ✓。有一条路走通了——前 6 个字符可以交错拼出。
判 dp[2][5]：s3 第 7 位是 'b'。两条路——从 s1 取 'a'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[2][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 7 位。
这一格只能走「上」这一条路：从 s1 取 'b' 去对 s3 第 3 位 'd'，对不上，还要看上格是否成立。
落子：dp[3][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 3 位。
判 dp[3][1]：s3 第 4 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[3][1] = ✓。有一条路走通了——前 4 个字符可以交错拼出。
判 dp[3][2]：s3 第 5 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[3][2] = ✓。有一条路走通了——前 5 个字符可以交错拼出。
判 dp[3][3]：s3 第 6 位是 'c'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[3][3] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
判 dp[3][4]：s3 第 7 位是 'b'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[3][4] = ✓。有一条路走通了——前 7 个字符可以交错拼出。
判 dp[3][5]：s3 第 8 位是 'c'。两条路——从 s1 取 'b'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[3][5] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 8 位。
这一格只能走「上」这一条路：从 s1 取 'c' 去对 s3 第 4 位 'b'，对不上，还要看上格是否成立。
落子：dp[4][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 4 位。
判 dp[4][1]：s3 第 5 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[4][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
判 dp[4][2]：s3 第 6 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[4][2] = ✓。有一条路走通了——前 6 个字符可以交错拼出。
判 dp[4][3]：s3 第 7 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[4][3] = ✓。有一条路走通了——前 7 个字符可以交错拼出。
判 dp[4][4]：s3 第 8 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[4][4] = ✓。有一条路走通了——前 8 个字符可以交错拼出。
判 dp[4][5]：s3 第 9 位是 'a'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
落子：dp[4][5] = ✓。有一条路走通了——前 9 个字符可以交错拼出。
这一格只能走「上」这一条路：从 s1 取 'c' 去对 s3 第 5 位 'b'，对不上，还要看上格是否成立。
落子：dp[5][0] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 5 位。
判 dp[5][1]：s3 第 6 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'd'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[5][1] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 6 位。
判 dp[5][2]：s3 第 7 位是 'b'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'b' 且来路成立，这格就 ✓。
落子：dp[5][2] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 7 位。
判 dp[5][3]：s3 第 8 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'b'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[5][3] = ✓。有一条路走通了——前 8 个字符可以交错拼出。
判 dp[5][4]：s3 第 9 位是 'a'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'c'（看左格），谁的字符对上 'a' 且来路成立，这格就 ✓。
落子：dp[5][4] = ✗。两条路都不通，这个前缀组合拼不出 s3 的前 9 位。
判 dp[5][5]：s3 第 10 位是 'c'。两条路——从 s1 取 'c'（看上格）或从 s2 取 'a'（看左格），谁的字符对上 'c' 且来路成立，这格就 ✓。
落子：dp[5][5] = ✓。有一条路走通了——前 10 个字符可以交错拼出。
右下角 dp[5][5] = ✓：用完 s1、s2 的全部字符，正好交错拼出整个 s3，所以答案是 true。
边界先想清。
两个高频追问。
参考代码
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]复杂度
- 时间：O(m·n)，每格 O(1)，共 (m+1)×(n+1) 格
- 空间：O(m·n)，整表；每格只依赖上格/左格，可滚动到 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么能用一维数组优化空间？
追问能 BFS / DFS+记忆化做吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
矩阵中的最长递增路径
LeetCode 329 · 困难 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题