LeetCode 97中等二维动态规划
交错字符串 图解题解
这道题到底在问什么
判断 s3 是否由 s1 和 s2 保持各自顺序交错组成。
- 示例
- s1="aab", s2="axy", s3="aaxaby" → true
最优解：一步一步想明白
- 3双指针贪心遇到相同字符会走错。
- 4dp[i][j] 表示 s1 前 i 个、s2 前 j 个能否组成 s3 前 i+j 个。
- 5列头是 s2、行头是 s1。dp[i][j] 问：用掉 s1 的前 i 个、s2 的前 j 个，能不能正好拼成 s3 的前 i+j 个字符？
- 6先填第 0 行：s1 一个不取，全靠 s2 去对 s3 的开头。
- 7再填第 0 列：s2 一个不取，全靠 s1。
- 8关键规则：dp[i][j] = (上方✓ 且 s1[i-1] 匹配) 或 (左方✓ 且 s2[j-1] 匹配)。两条来路取「或」。
- 9逐格套「上方或左方」规则填。
- 10填到右下角。
- 11绿色路径 (0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(3,2)→(3,3) 就是一种拼法：向下一格=取一个 s1，向右一格=取一个 s2。
- 14一句话记住：dp[i][j] 表示 s1 前 i 个、s2 前 j 个能否组成 s3 前 i+j 个。
- 23这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：忘了 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 基)。
完整代码（Python / C++ / Java）
Python
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]C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
int m=s1.size(), n=s2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][0] = true;
for (int i=0;i<=m;i++) for (int j=0;j<=n;j++) {
int k = i + j - 1;
if (i>0) dp[i][j] |= dp[i-1][j] && s1[i-1] == s3[k];
if (j>0) dp[i][j] |= dp[i][j-1] && s2[j-1] == s3[k];
}
return dp[m][n];
}
};Java
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) return false;
int m=s1.length(), n=s2.length();
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++) {
int k = i + j - 1;
if (i>0) dp[i][j] |= dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k);
if (j>0) dp[i][j] |= dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k);
}
return dp[m][n];
}
}套路模板 · 二维 DP（交错字符串）
# 交错字符串骨架 · 二维 DP
if len(s1)+len(s2) != len(s3): return False
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] # 上方:取 s1
if j>0: dp[i][j] |= dp[i][j-1] and s2[j-1]==s3[k] # 左方:取 s2
return dp[m][n]复杂度
时间复杂度
O(m·n)
填满 (m+1)×(n+1) 张表，每格 O(1)
空间复杂度
O(m·n)
dp 二维表；只依赖上一行，可滚动压到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 交错字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心状态是什么？+
dp[i][j] = s1 前 i 个、s2 前 j 个能否交错组成 s3 前 i+j 个；答案是 dp[m][n]。
这道题为什么用「二维动态规划」，换最直接的暴力解会差在哪？+
二维动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。