交错字符串
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + ...或者t1 + s1 + t2 + s2 + ...
注意：a + b 表示字符串 a 和 b 连接。
示例 1
示例 2
示例 3
模拟答题者思考
1. 暴力想法：递归枚举每一步从 s1 还是 s2 取下一个字符，与 s3 当前位比对——正确，但分支指数级，长度上百会超时。
2. 重复在哪里？状态只取决于「已用 s1 前几个、已用 s2 前几个」，与具体交错路径无关；同一对 (i,j) 会被不同递归路径反复访问。
3. 子问题定义：设 dp[i][j] 表示两前缀能否拼成 s3 的前 i+j 个。最后字符若来自 s1，需 dp[i-1][j] 成立且 s1[i-1]==s3[i+j-1]；若来自 s2，对称。二者取或。
4. 手推示例 1 一角：s1="aabcc"、s2="dbbca"、s3="aadbbcbcac"。dp[1][0] 由 s1[0]='a' 与 s3[0]='a' 得真；再与 s2 交错延伸，最终 dp[5][5] 为真。
5. 与编辑距离对比：同样是「双串 + 二维 DP」，但本题没有「删插替」代价，只有「选左串还是右串的下一个字符」且必须全匹配；边界是沿第一行/列单串匹配 s3 前缀。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dp[i][j] | bool[][] | 定义：s1 的前 i 个字符与 s2 的前 j 个字符能否交错拼成 s3 的前 i+j 个字符维护：最后一步要么从 s1 再取一个字符，要么从 s2 再取一个；对应 s3 的第 i+j 个字符（下标 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])；答案 dp[m][n] |
i, j | int | 定义：已消耗的 s1 / s2 前缀长度，范围 0..m、0..n维护：交错后总长度恒为 i+j，与 s3 前缀一一对应更新：双重循环 i=0..m、j=0..n；边界行 j=0 只走 s1，边界列 i=0 只走 s2 |
m, n | int | 定义：len(s1)、len(s2)维护：若 len(s3) != m+n 可直接返回 false更新：只读； 0 ≤ m,n ≤ 100 |
落码步骤
1. 令 m,n = len(s1), len(s2)；若 len(s3) != m+n，返回 false
2. 建 (m+1)×(n+1) 布尔表，dp[0][0]=true
3. 初始化第一列 dp[i][0]：仅 s1 前缀对齐 s3 前 i 位
4. 初始化第一行 dp[0][j]：仅 s2 前缀对齐 s3 前 j 位
5. 对 i=1..m、j=1..n 按转移式填 dp[i][j]
6. 返回 dp[m][n]
代码实现
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if len(s3) != m + n:
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (
dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
) or (
dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
)
return dp[m][n]class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if ((int)s3.size() != m + n) return false;
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 1; i <= m; ++i)
dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];
for (int j = 1; j <= n; ++j)
dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
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]);
}
}
return dp[m][n];
}
};
// 时间 O(mn)，空间 O(mn)；进阶可压成 O(n) 滚动复杂度分析
O(m × n)（m=len(s1)，n=len(s2)）
O(m × n)（二维 dp；可滚动为一维 O(n)）
常见坑
忘记长度预判：len(s3) ≠ len(s1)+len(s2) 时一定为 false，否则 s3[i+j-1] 会越界或漏判。
s3 下标写错：交错总长为 i+j，当前字符是 s3[i+j-1]，不是 s3[i-1] 或 s3[j-1]。
边界只初始化 dp[0][0]：第一行/列表示「完全来自单串」，必须逐位与 s3 前缀比对，不能默认全 true。
必测边界 Case
s1="", s2="", s3="" → true
s1="a", s2="", s3="a" → true；s3="b" → false
s1="a", s2="b", s3="a" → false（总长应为 2）
s3="aadbbbaccc" → false（多一个 b，无法与两源串对齐）