§1

题目描述

判断 s3 是否由 s1 和 s2 保持各自顺序交错组成。

示例 = s1="aab", s2="axy", s3="aaxaby" → true

§2

思路解析动画文字版

双指针贪心遇到相同字符会走错。

dp[i][j] 表示 s1 前 i 个、s2 前 j 个能否组成 s3 前 i+j 个。

1. 定义状态 · dp[0][0]=✓：列头是 s2、行头是 s1。dp[i][j] 问：用掉 s1 的前 i 个、s2 的前 j 个，能不能正好拼成 s3 的前 i+j 个字符？

2. 第 0 行：只取 s2：先填第 0 行：s1 一个不取，全靠 s2 去对 s3 的开头。

3. 第 0 列：只取 s1：再填第 0 列：s2 一个不取，全靠 s1。

4. 关键帧 · 内部格的两条来路：关键规则：dp[i][j] = (上方✓ 且 s1[i-1] 匹配) 或 (左方✓ 且 s2[j-1] 匹配)。两条来路取「或」。

5. 按规则继续填：逐格套「上方或左方」规则填。

6. 填到最后一行：填到右下角。

7. 关键帧 · 答案 + 路径：绿色路径 (0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(3,2)→(3,3) 就是一种拼法：向下一格=取一个 s1，向右一格=取一个 s2。

一句话记住：dp[i][j] 表示 s1 前 i 个、s2 前 j 个能否组成 s3 前 i+j 个。

边界三连：三种边界先想清楚再写。

面试追问 1：核心状态先讲清。

面试追问 2：转移方向是得分点。

面试追问 3：空间优化是加分项。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。

§3

参考代码

class Solution:    def isInterleave(self, s1, s2, s3):        if len(s1) + len(s2) != len(s3):            return False        m, n = len(s1), len(s2)        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):                k = i + j - 1                if i > 0:                    dp[i][j] |= dp[i - 1][j] and s1[i - 1] == s3[k]                if j > 0:                    dp[i][j] |= dp[i][j - 1] and s2[j - 1] == s3[k]        return dp[m][n]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(m·n)，填满 (m+1)×(n+1) 张表，每格 O(1)
空间复杂度：O(m·n)，dp 二维表；只依赖上一行，可滚动压到 O(n)

§5

可套用的代码模板

骨架就是双层循环填表，每格取「上方(用s1)或左方(用s2)」两条来路的或。

Python

# 交错字符串骨架 · 二维 DPif len(s1)+len(s2) != len(s3): return Falsedp[0][0] = Truefor i in range(m+1):    for j in range(n+1):        k = i + j - 1        if i>0: dp[i][j] |= dp[i-1][j] and s1[i-1]==s3[k]  # 上方:取 s1        if j>0: dp[i][j] |= dp[i][j-1] and s2[j-1]==s3[k]  # 左方:取 s2return dp[m][n]

§6

易错点

✗ 错误写法：忘了 dp[0][0]=true

✓ 正确写法：空+空=空，是 true 起点

不设起点，整张表推不出任何 true。

✗ 错误写法：没先判长度

✓ 正确写法：len(s1)+len(s2)≠len(s3) 直接 false

长度对不上根本不可能交错，先挡掉省事。

✗ 错误写法：s3 下标算错

✓ 正确写法：当前 s3 字符下标 = i+j−1

(i,j) 表示已用掉 i+j 个字符，正在匹配第 i+j−1 个(0 基)。

面试追问把动画讲成自己的话

追问这题的核心状态是什么？

dp[i][j] = s1 前 i 个、s2 前 j 个能否交错组成 s3 前 i+j 个；答案是 dp[m][n]。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 二维动态规划 7/15

矩阵中的最长递增路径

LeetCode 329 · 困难 · 沿着二维动态规划继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Solution: def isInterleave(self, s1, s2, s3): if len(s1) + len(s2) != len(s3): return False m, n = len(s1), len(s2) 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): k = i + j - 1 if i > 0: dp[i][j] |= dp[i - 1][j] and s1[i - 1] == s3[k] if j > 0: dp[i][j] |= dp[i][j - 1] and s2[j - 1] == s3[k] return dp[m][n]

# 交错字符串骨架 · 二维 DPif len(s1)+len(s2) != len(s3): return Falsedp[0][0] = Truefor i in range(m+1): for j in range(n+1): k = i + j - 1 if i>0: dp[i][j] |= dp[i-1][j] and s1[i-1]==s3[k] # 上方:取 s1 if j>0: dp[i][j] |= dp[i][j-1] and s2[j-1]==s3[k] # 左方:取 s2return dp[m][n]