LeetCode 97. 交错字符串

约 6 分钟
文章信息 17 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需加强 历史考题 20-50 字节跳动 微软 美团 阿里巴巴 腾讯 滴滴 京东 拼多多 虾皮 面试经典 150 题
标签
字符串 动态规划 动态规划经典题
目录

题目描述

✅ 97. 交错字符串

考察公司：美团

考察时间：2025.5.28

image-20250528202233985

image-20250528202306724

image-20250528202353379

题意分析

给定三个字符串 s1、s2、s3，判断 s3 是否由 s1 和 s2 交错组成。所谓交错，是指把 s1 和 s2 各自切成若干段，再交替拼接起来。关键约束是：s1 内部的字符必须保持原有的先后顺序，s2 内部同理，两者之间的相对位置则可以任意穿插。

换个更好操作的说法：想象两个指针分别指向 s1 和 s2 的开头，每一步从其中一个指针处取走一个字符追加到结果末尾。若存在某种取法能拼出 s3，答案就是 true。这个描述把「切段」这种模糊的表述转化成了「逐字符决策」，也就把问题变成了可以逐步推进的形式。

约束信号有几条。第一，三个串长度都在 100 以内，$O(mn)$ 甚至 $O(mn)$ 带常数都完全够用，不需要贪心式的精巧构造。第二，s1 和 s2 可以为空串，空串与任意串交错就是那个串本身。第三，字符可以重复，比如 s1 和 s2 开头都是 a 而 s3 也以 a 开头，这时两条路都得走，无法靠「谁匹配就选谁」的贪心决定——这一点直接排除了双指针贪心。

边界方面，最容易被忽略的是长度关系：任何一次取字符都会让两个指针的总推进量加一，所以只有 s1.length + s2.length == s3.length 时才可能成立。这不是优化，而是必须先做的正确性前提，否则后面所有下标运算都会错位甚至越界。

解法：一维前缀动态规划

核心思路

问题关键：每一步可能从 s1 或 s2 取字符，遇到相同字符时不能贪心；但走到同一对前缀长度 (i,j) 后，后续问题完全相同，因此应合并重复状态。

状态与推导：定义 D[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符，能否组成 s3 前 i+j 个字符。s3 的进度可由 i+j 推出，不需要第三维。最后一个字符只有两种来源：

D[i][j] = (D[i-1][j] && s1[i-1] == s3[i+j-1]) || (D[i][j-1] && s2[j-1] == s3[i+j-1])

为什么压成一维：当前行只依赖上一行同列和当前行左侧。令 dp[j] 滚动表示 D[i][j]；按 j 从小到大更新时，赋值前的 dp[j] 是 D[i-1][j]，更新后的 dp[j-1] 是 D[i][j-1]，两项都恰好可用。

不变量与正确性：处理到 (i,j) 时，dp[j] 为真当且仅当两个对应前缀能交错得到 s3 的等长前缀。转移完整枚举最后一个字符来自哪条串，并要求来源字符匹配且较短前缀已可达，所以既不会接受非法顺序，也不会漏掉合法取法。最终 dp[n] 就是完整字符串的答案。

解题步骤

  1. 若 m+n != s3.length，直接返回 false，否则状态下标可能越界且必然无解。
  2. 令 dp[0] = true，初始化只使用 s2 的第一行；前缀一旦不匹配，后续状态自然保持 false。
  3. 逐行加入 s1[i-1]：先更新只使用 s1 的 dp[0]，再让 j 从 1 递增，按两种字符来源更新 dp[j]。
  4. 返回 dp[n]。

口述样例：s1="ab", s2="a", s3="aab"。初始化行是 [T,T]；加入 s1[0]='a' 后仍为 [T,T]；加入 s1[1]='b' 后为 [F,T]，最终可达。

边界与反例：空串由首行或首列自然覆盖。贪心反例是 s1="aa", s2="ab", s3="aaba"：若前两个 'a' 都优先取自 s1 会卡住，但先取 s2 的 'a' 存在合法方案。

代码实现

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(mn)$，每个前缀组合只计算一次。
  • 空间复杂度：$O(n)$，n 为 s2 长度；若先让较短字符串作为 s2，可写成 $O(\min(m,n))$。

关键点总结

  • 两个前缀长度已唯一决定第三个串的进度 i+j。
  • 转移按「最后一个字符来自谁」分成两支，二者是或关系。
  • 一维压缩时 dp[j] 是上一行旧值，dp[j-1] 是当前行新值，因此必须正序更新。
  • 长度校验既是必要条件，也避免访问 s3[i+j-1] 时越界。

易错点总结

  • 忘记长度校验：可能误判，且 s3[i+j-1] 会越界。
  • 将目标下标写成 i-1 或 j-1；两个前缀共消耗 i+j 个字符，正确下标是 i+j-1。
  • 一维数组倒序更新：dp[j-1] 会变成上一行状态，而转移需要当前行左侧状态。
  • 每行开头不更新 dp[0]：会错误地认为任意 s1 前缀都能匹配。
  • 只比较当前字符、不检查前驱状态：会破坏两个原字符串各自的相对顺序。

相似题目

题目 难度 考察点
72. 编辑距离 中等 同为两串前缀状态，但转移是增删改三支取最小值而非布尔可达性
583. 两个字符串的删除操作 中等 只允许删除，答案等价于总长减去两倍最长公共子序列
712. 两个字符串的最小ASCII删除和 中等 删除的代价按字符 ASCII 加权，不能再按删除次数计数
1035. 不相交的线 中等 几何连线问题伪装的最长公共子序列，难点是识别出模型
1143. 最长公共子序列 中等 求最优值而非判定，字符不等时取两侧最大值而不是直接置 false
LCR 095. 最长公共子序列 中等 与 1143 同题，可用来练习一维压缩时暂存左上角值的技巧
LCR 096. 交错字符串 中等 与本题同题，适合再练一遍长度校验与一维滚动的遍历方向