LeetCode 97. 交错字符串
题目描述
:::fold 历史考题
考察公司：美团
考察时间：2025.5.28
:::
题意分析
判断是否能把
s1、s2的全部字符交错合并成s3，要求每个来源字符串内部的字符先后顺序保持不变，不能删除、重复使用或重新排序字符。可以连续从同一个来源取多个字符，不要求每取一个字符就切换来源；这些连续字符自然组成同一段。因此总长度必须满足
s1.length + s2.length == s3.length。只需判断是否存在一种合并方式，来源当前字符相同时不能随意固定选择一边。
解法：一维前缀动态规划
核心思路
[!blue]
令
D[i][j]表示s1的前i个字符和s2的前j个字符，能否交错组成s3的前i + j个字符。两个来源已经使用的长度确定后，目标的进度也随之确定，所以不需要再增加一个目标下标维度。对非空前缀，目标最后一个字符位于
s3[i + j - 1]，它只有两种来源。如果来自s1，必须有D[i - 1][j]成立，并且s1[i - 1]等于目标字符；如果来自s2，必须有D[i][j - 1]成立，并且s2[j - 1]等于目标字符。任一来源成立即可，两者用逻辑或连接。检查前驱状态，保证此前的字符也已经按合法顺序拼好。边界
D[0][0] = true表示两个空来源能组成空目标。首行只允许使用s2，首列只允许使用s1，因此沿对应来源逐字检查前缀是否完全相等；一旦前缀失配，后面的首行或首列状态也都不再可达。转移只依赖上一行同列和本行左侧，可以压缩为一维
dp。每行先更新dp[0]，再从左向右更新其他位置：旧dp[j]仍是D[i - 1][j]，对应从s1追加；已经更新的dp[j - 1]是D[i][j - 1]，对应从s2追加。先用两个来源条件计算结果，再覆盖当前状态。当字符同时可以来自两边时，动态规划保留两个前驱的可达性，不必提前做不可撤回的选择。处理完全部前缀后，
dp[n]才表示两个来源都已用完、完整目标可以组成。
解题步骤
- 记两条来源串长度为
m、n；若总长度不等于目标长度，直接返回false。- 创建长度为
n + 1的布尔数组，令dp[0] = true，依次初始化只使用s2的各个前缀状态。- 外层枚举
s1前缀长度i，先更新只使用s1的dp[0]。- 内层让
j从1到n，取目标字符s3[i + j - 1]，分别判断来自s1和s2的前驱是否可行，再用逻辑或写回dp[j]。- 返回
dp[n]；任意来源为空时，首行或首列的初始化会自然覆盖这类情况。
代码实现
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length();
int n = s2.length();
if (m + n != s3.length()) {
return false;
}
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int j = 1; j <= n; j++) {
dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char target = s3.charAt(i + j - 1);
// 当前位置保留上一行旧值，左侧已更新为本行，各自对应一个来源。
boolean fromS1 = dp[j] && s1.charAt(i - 1) == target;
boolean fromS2 = dp[j - 1] && s2.charAt(j - 1) == target;
dp[j] = fromS1 || fromS2;
}
}
return dp[n];
}
}
func isInterleave(s1 string, s2 string, s3 string) bool {
m := len(s1)
n := len(s2)
if m+n != len(s3) {
return false
}
dp := make([]bool, n+1)
dp[0] = true
for j := 1; j <= n; j++ {
dp[j] = dp[j-1] && s2[j-1] == s3[j-1]
}
for i := 1; i <= m; i++ {
dp[0] = dp[0] && s1[i-1] == s3[i-1]
for j := 1; j <= n; j++ {
target := s3[i+j-1]
// 当前位置保留上一行旧值，左侧已更新为本行，各自对应一个来源。
fromS1 := dp[j] && s1[i-1] == target
fromS2 := dp[j-1] && s2[j-1] == target
dp[j] = fromS1 || fromS2
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O((m + 1)(n + 1))$，每对前缀长度只计算一次；包含首行、首列和空串边界，两串非空时通常写作 $O(mn)$。
- 空间复杂度：$O(n + 1)$，保存
s2方向的一行状态及空前缀边界。
关键点总结
[!green]
- 两个来源的已用前缀长度，既约束各自顺序，也唯一确定目标进度。
- 最后一个字符可以来自任意一边，必须同时检查对应前驱和当前字符。
- 一维数组正序更新，才能分别读取上一行同列与本行左侧的状态。
- 初始化解决空来源，完整状态
dp[n]才能确保所有字符都被使用。
易错点总结
[!yellow]
- 省略长度校验，可能漏掉未使用的字符，也可能在访问目标位置时越界。
- 将目标下标写成单个来源的进度；两个前缀一共使用
i + j个字符，末尾下标应为i + j - 1。- 一维数组倒序更新，左侧值仍来自上一行，不再对应从当前
s2前缀追加字符的转移。- 每行不更新
dp[0]，会沿用旧的仅使用s1的前缀匹配结果。- 只比较当前字符，不检查此前前缀是否可达，无法保证完整顺序正确。
- 两个来源当前字符都匹配时固定优先一边，可能让后面的字符无法衔接；应保留两种可达来源。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同样在两个字符串的前缀坐标上转移，本题还要求选取顺序拼成第三个串且用完全部字符。 |
| 115. 不同的子序列 | 困难 | 同样按前缀消费字符，原题从一个串中选出目标并计数，本题从两个来源交错构成目标。 |