LeetCode LCR 096. 交错字符串

2026-03-28 HGNULB 约 11 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 096. 交错字符串

题意分析

给定三个字符串 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 时才可能成立。这不是优化，而是必须先做的正确性前提，否则后面所有下标运算都会错位甚至越界。

解法：一维前缀动态规划

核心思路

先看暴力。按上面的「逐字符决策」描述，写一个递归 dfs(i, j)：已经用掉 s1 的前 i 个和 s2 的前 j 个字符，问剩下的能否拼出 s3 的剩余部分。每一层有两种选择——取 s1[i] 或取 s2[j]，于是搜索树是一棵二叉树，深度为 m + n，最坏 $O(2^{m+n})$。瓶颈在于大量重复：走「先取 s1 再取 s2」和「先取 s2 再取 s1」，最终落到的状态都是 (i+1, j+1)，后续问题完全一样却被重算了两遍。

这正是记忆化/动态规划的入口：状态只由 (i, j) 决定，而 (i, j) 只有 $(m+1)(n+1)$ 种。更重要的一个观察是——s3 中已经被消耗掉的长度必然是 i + j，不需要第三维记录 s3 的进度。这个「三维压二维」的观察是本题的核心，说不出它就等于没理解为什么是二维 DP。

于是定义状态：

dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符，能否交错组成 s3 的前 i + j 个字符。答案是 dp[m][n]。

转移看 s3[i + j - 1]（即当前要填的最后一个字符）是从哪个串取来的，只有两种可能：

第一支，来自 s1。含义是：最后一步取走了 s1 的第 i 个字符，那么在此之前必须已经用 s1 的前 i - 1 个和 s2 的前 j 个拼出了 s3 的前 i + j - 1 个，并且这个字符要对得上。写成 dp[i][j] |= dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]。

第二支，来自 s2。对称地，最后一步取走 s2 的第 j 个字符，要求 dp[i][j] |= dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]。

两支是「或」的关系，因为只要有一种取法能成就算成立。边界 dp[0][0] = true，表示两个空前缀能拼出空串。

最后做空间压缩。dp[i][j] 只依赖同一行的 dp[i][j - 1] 和上一行的 dp[i - 1][j]，所以可以只留一行滚动。按 j 递增更新时，dp[j] 在被赋值前还保存着上一行的值，正好是「来自 s1」那一支需要的 dp[i - 1][j]；而 dp[j - 1] 已经在本轮被更新过，是「来自 s2」那一支需要的 dp[i][j - 1]。同一个数组里的新旧值恰好对应两个转移来源，这也是这份代码最需要讲清楚的地方。

解题步骤

先判断 s1.length() + s2.length() != s3.length()，不等直接返回 false。原因是每取一个字符两侧总进度加一，长度对不上时根本不存在合法的取法，而且后续 s3.charAt(i + j - 1) 会越界。

开一个长度 n + 1 的布尔数组代表 dp 的一行，令 dp[0] = true。这是 dp[0][0]，即两个空前缀能拼出空串。

初始化第一行：对 j 从 1 到 n，令 dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1]。这一行代表完全不使用 s1，所以 s3 的前 j 位必须逐字符等于 s2 的前 j 位，一旦断了后面就全是 false。

外层枚举 i 从 1 到 m，代表把 s1 的前 i 个字符纳入考虑，也就是从上一行推进到当前行。

每行开头先更新 dp[0] = dp[0] && s1[i - 1] == s3[i - 1]。它对应 dp[i][0]，即完全不使用 s2 的情形，只能由 dp[i - 1][0] 这一支转移而来。这一步必须放在内层循环之前，因为 dp[0] 是本行 dp[1] 的依赖。

内层 j 从 1 递增到 n，取 target = s3[i + j - 1]，分别算出 fromS1 = dp[j] && s1[i - 1] == target 与 fromS2 = dp[j - 1] && s2[j - 1] == target，再写回 dp[j] = fromS1 || fromS2。递增方向是必须的：dp[j] 此刻仍是上一行的旧值，读完立刻覆盖；dp[j - 1] 此刻已是本行的新值。

循环结束后返回 dp[n]，它就是 dp[m][n]。

以 s1 = "ab", s2 = "a", s3 = "aab" 走一遍。长度校验：2 + 1 == 3，通过。数组长度为 2，下面用 [dp[0], dp[1]] 记录每一行结束时的状态。

初始化第一行（i = 0，不用 s1）：dp[0] = true；j = 1 时 dp[1] = dp[0] && s2[0]='a' == s3[0]='a'，成立，得到 true。此行为 [T, T]，含义是「只用 s2 的前 0 或前 1 位能拼出 s3 的前 0 或前 1 位」。

i = 1（纳入 s1 的 'a'）：先更新 dp[0] = dp[0](T) && s1[0]='a' == s3[0]='a' → true。再看 j = 1，target = s3[1] = 'a'；fromS1 = dp[1]（旧值 T，即 dp[0][1]）&& s1[0]='a' == 'a' → true；fromS2 = dp[0]（新值 T，即 dp[1][0]）&& s2[0]='a' == 'a' → true；写回 dp[1] = true。此行为 [T, T]。

i = 2（纳入 s1 的 'b'）：先更新 dp[0] = dp[0](T) && s1[1]='b' == s3[1]='a' → false，因为只用 "ab" 拼不出 "aa"。再看 j = 1，target = s3[2] = 'b'；fromS1 = dp[1]（旧值 T，即 dp[1][1]）&& s1[1]='b' == 'b' → true；fromS2 = dp[0]（新值 F）→ false；写回 dp[1] = true。此行为 [F, T]。

返回 dp[1] = true。核对一下：取 s2 的 'a'、s1 的 'a'、s1 的 'b'，正好拼出 "aab"，答案正确。

代码实现

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);
                // 当前字符可以来自 s1，也可以来自 s2，任一来源成立即可。
                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]
            // dp[j] 表示来自 s1，dp[j-1] 表示来自 s2。
            fromS1 := dp[j] && s1[i-1] == target
            fromS2 := dp[j-1] && s2[j-1] == target
            dp[j] = fromS1 || fromS2
        }
    }
    return dp[n]
}

复杂度分析

时间复杂度：$O(mn)$。状态数是 $(m+1)(n+1)$ 个 (i, j) 组合，每个状态只做两次字符比较和一次布尔运算，是常数代价，因此总量与状态数同阶。

空间复杂度：$O(n)$。二维表的每一行只依赖上一行和本行左侧，压缩成一维滚动数组后只需 n + 1 个布尔值，与 m 无关；若不压缩则是 $O(mn)$。

关键点总结

双序列问题的第一反应就是「两个前缀长度作为状态」。本题的额外亮点是发现第三个串的进度可由 i + j 推出，从而把看似三维的问题降到二维——遇到多序列同步推进时都该先找这类可推导的冗余维度。

转移的分支应该按「最后一步是什么」来枚举，而不是按「下一步怎么走」。倒着想能让每一支直接落到一个更小的已知状态上，转移式自然成立。

一维压缩不是无脑改写，遍历方向由依赖方向决定。本题依赖上一行同列和本行左侧，所以必须递增；若依赖本行右侧则必须递减。写之前先问一句「我要读的是新值还是旧值」。

长度和不等这类必要条件应当在算法开始前作为前置校验，而不是指望 DP 自己算出 false。它同时承担正确性与防越界两个职责。

面试视角：这题的标准考法是先让你写出递归加记忆化，再追问「能不能优化空间」。能把 dp[j] 是旧值、dp[j - 1] 是新值这件事当场说清楚，是区分「背过代码」和「真懂 DP」的分水岭，建议主动讲。

面试视角：如果面试官问「能不能贪心，谁匹配就取谁」，要能立刻给出反例——s1 = "aa"、s2 = "ab"、s3 = "aaba" 时前两位都可以从任一串取 'a'，优先取 s1 会在第三位卡死，而正确答案是 true。举得出反例比说「贪心不对」有力得多。

易错点总结

错误写法：不先判断 s1.length() + s2.length() == s3.length() 就进入 DP。用例 s1 = "ab", s2 = "a", s3 = "aa" → 循环中访问 s3.charAt(i + j - 1)，当 i = 2, j = 1 时下标为 2 而 s3 只有 2 个字符，直接抛出越界异常；即使侥幸不越界，结果也可能误判为 true。这是本题最高频的错误。

错误写法：把 s3 的下标写成 s3.charAt(j - 1) 或 s3.charAt(i - 1)，忘了两个前缀共同贡献长度。用例 s1 = "ab", s2 = "a", s3 = "aab" → 内层比较的一直是 s3 的前几位，i = 2, j = 1 时该比 s3[2]='b' 却比了 s3[0]='a'，返回 false。除去第一行和第一列的特例，正文下标恒为 i + j - 1。

错误写法：一维压缩时内层 j 从大到小遍历。用例 s1 = "a", s2 = "bc", s3 = "abc" → 先算 j = 2 时读到的 dp[1] 还是上一行的 false，而本行的 dp[1] 应该是 true，「来自 s2」那一支的前驱状态错行，返回 false，正确答案是 true。依赖本行左侧就必须递增。

错误写法：忘记在每行开头更新 dp[0]，让它一直保持初始的 true。用例 s1 = "x", s2 = "y", s3 = "yy" → dp[0] 恒为 true 等于无条件承认「只用 s1 的前 i 位就能拼出 s3 的前 i 位」，于是 dp[1][1] 经由 s2[0]='y' == s3[1]='y' 被置为 true，返回 true，而正确答案是 false。

错误写法：把 dp[0] 的更新放在内层循环之后。用例任意 m, n >= 1 → 本行的 dp[1] 读 dp[0] 时拿到的还是上一行的值，「来自 s2」这一支的前驱状态错行，结果不可预测。

错误写法：两支转移用「与」连接，写成 dp[j] = fromS1 && fromS2。用例 s1 = "a", s2 = "b", s3 = "ab" → 要求当前字符同时能由两个串提供，几乎总是 false。交错是「存在一种取法」，天然是或的语义。

错误写法：只比较字符相等而不检查前驱状态，写成 dp[j] = s1[i-1] == target || s2[j-1] == target。用例 s1 = "ab", s2 = "c", s3 = "bac" → 末位 'c' 与 s2[0] 相同就把 dp[2][1] 置成 true 返回 true，但 "bac" 里 'b' 排在 'a' 前面，违反了 s1 的内部顺序，正确答案是 false。丢掉「之前也得拼得出来」这个前驱约束，DP 就退化成了字符集比较。

错误写法：第一行初始化时逐位独立判断，写成 dp[j] = s2[j-1] == s3[j-1]，漏掉 dp[j - 1] &&。用例 s1 = "", s2 = "ab", s3 = "cb" → dp[2] 因为末位 'b' 相同被置为 true，但前缀早已断裂，正确答案是 false。第一行必须是前缀式的连乘。

错误写法：用双指针贪心，哪个串的当前字符与 s3 相同就取哪个。用例 s1 = "aa", s2 = "ab", s3 = "aaba" → 前两位都可以从任一串取 'a'，若优先取 s1 则 s1 提前耗尽，走到 s3[2] = 'b' 时只剩 s2[0] = 'a'，返回 false，而正确答案是 true。有分歧就必须搜索或 DP。

错误写法：认为 s1、s2 为空是特殊情况需要单独 if 处理。用例 s1 = "", s2 = "abc", s3 = "abc" → 单独处理容易与主逻辑不一致而写错。实际上 m = 0 时外层循环不执行，答案直接由第一行初始化给出，主逻辑本身已经覆盖，多写反而增加出错面。

相似题目

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