LeetCode LCR 096. 交错字符串

约 5 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR

题目描述

✅ LCR 096. 交错字符串

image-20260929004258706

image-20260929004258708

题意分析

判断能否把 s1、s2 的全部字符交错组成 s3。每一步可以从某个来源串取下一个字符，但各来源内部的顺序必须保持，不能跳过或重复使用字符。

因此两来源的长度之和必须等于目标长度。遇到两边字符都能匹配时，不能随意固定其中一边，因为它们剩余的内容不同，需要保留两种可能。任意来源串也允许为空。

解法：滚动数组判断交错前缀

核心思路

[!blue]

设 f[i][j] 表示 s1 前 i 个字符与 s2 前 j 个字符，能否组成 s3 前 i + j 个字符。来源用了多少字符，就必须生成多少目标字符，所以目标进度由 i + j 唯一确定，不需要第三个状态维度。

考察当前目标末位 s3[i + j - 1] 的来源：若来自 s1，要求 f[i - 1][j] 可行，且 s1[i - 1] 与目标字符相等；若来自 s2，要求 f[i][j - 1] 可行，且 s2[j - 1] 与目标字符相等。两种来源穷尽最后一步，满足任意一种即可，因此取逻辑或。

两个空前缀可以组成空串，故 f[0][0] = true。只使用一个来源时，没有选择余地，必须逐字符匹配目标前缀；这就是第一行与第一列的初始化方式。

转移只依赖上一行同列与本行左侧，可以压成一行 dp。从左到右更新时，尚未覆盖的 dp[j] 是 f[i - 1][j]，已经更新的 dp[j - 1] 是 f[i][j - 1]，正好对应两种来源。每行先更新 dp[0]，才能让第一列读取本行的正确边界。

完成全部来源字符后，dp[n] 就是 f[m][n]。前置长度检查保证此时既没有缺少目标字符，也没有留下多余字符。

解题步骤

  1. 两来源长度之和不等于目标长度时，直接返回 false。
  2. 创建 n + 1 个布尔状态，令 dp[0] = true，再用 s2 初始化只使用第二个来源的第一行。
  3. 每处理 s1 的一个字符，先更新 dp[0]，表示只使用 s1 的当前前缀。
  4. 按 j 递增，分别判断来自旧上方与新左方的两种可能，用逻辑或覆盖 dp[j]。
  5. 返回 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);
                // 当前字符可以来自 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((m + 1)(n + 1))$，包含第一行、第一列的初始化，也覆盖某个来源为空的情况。
  • 空间复杂度：$O(n + 1)$，保存第二个来源前缀长度对应的一行状态。

关键点总结

[!green]

  • 两个来源前缀长度确定目标前缀长度，状态不需要记录第三个进度。
  • 每种来源都要同时满足“此前可行”和“当前字符相同”，两种来源之间取或。
  • 滚动数组读的是旧上方与新左方，因此必须从左到右更新。
  • 长度校验和空前缀初始化共同保证所有字符恰好被使用。

易错点总结

[!yellow]

  • 先检查两来源串的总长度等于目标长度，再访问目标的 i+j-1 位置。
  • 两种来源是或关系，但每种都要同时满足对应前驱可达和当前字符相等。
  • 一维数组每行先更新 dp[0]，再从左向右更新，保持旧上方与新左方的语义。

相似题目

题目 难度 关联与区别
1143. 最长公共子序列 中等 同样在两个字符串的前缀坐标上转移，本题还要求选取顺序拼成第三个串且用完全部字符。
115. 不同的子序列 困难 同样按前缀消费字符，原题从一个串中选出目标并计数，本题从两个来源交错构成目标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/47313550
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！