LeetCode 115. 不同的子序列

约 5 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 20-50 字节跳动 微软 美团 阿里巴巴 腾讯 百度 网易 小米
标签
字符串 动态规划
目录

题目描述

✅ 115. 不同的子序列

题意分析

给两个字符串 s 和 t，问在 s 里有多少种方式删掉若干字符（可以一个都不删）之后，剩下的内容恰好等于 t。这里的「若干」包含零个，剩余字符必须保持原来的相对顺序。

关键在于统计的口径：两种方案是否算不同，看的是被保留下来的下标集合，而不是拼出来的字符串。s = "aab"、t = "ab" 时，保留下标 {0, 2} 和保留下标 {1, 2} 拼出的都是 "ab"，但它们算两种不同方案，答案是 2。这一点决定了本题是计数题而不是判定题。

约束给了两条信号。字符串长度在千级别，说明可以接受长度乘积量级的算法，但不能接受指数级的枚举；题目还保证最终答案落在 32 位有符号整数范围内，这句话反过来提醒：中间过程可能溢出，因为部分前缀的方案数并不一定受这个保证约束。

边界要单独想清楚。t 为空串时，唯一的方式是把 s 全部删光，方案数是 1 而不是 0；s 比 t 短时不可能匹配，答案是 0；s 与 t 完全相同时答案是 1；s 全是同一个字符、t 是它的一段时，答案是组合数，会迅速变得很大。

解法：一维前缀计数动态规划

核心思路

先从二维状态推导。定义 f[i][j]：只使用 s 的前 i 个字符，得到 t 的前 j 个字符共有多少种下标选择。

处理 s[i - 1] 时：

  • 不选择它，方案数是 f[i - 1][j]；
  • 若 s[i - 1] == t[j - 1]，还可以选择它匹配目标末尾，方案数是 f[i - 1][j - 1]。

两类方案按“是否使用当前字符”划分，互斥且覆盖全部情况，因此

$f[i][j] = f[i - 1][j] + f[i - 1][j - 1]$（字符相等），否则 $f[i][j] = f[i - 1][j]$。

初值是 f[i][0] = 1：从任意前缀得到空串只有“全部不选”这一种方式；f[0][j] = 0（j > 0）。

每一行只依赖上一行，可以压缩为一维 dp[j]。更新时必须让 j 从大到小遍历：这样读取的 dp[j - 1] 仍是上一轮的值，当前 s 字符只会被使用一次。若正序更新，同一个字符可能同时匹配 t 的多个位置。

解题步骤

  1. 创建长度为 t.length() + 1 的 dp，令 dp[0] = 1。
  2. 从左到右扫描 s。处理第 i 个字符时，dp[j] 表示当前源串前缀组成 t 前 j 个字符的方案数。
  3. 令 j 从 min(i + 1, t.length()) 倒序到 1。字符相等时执行 dp[j] += dp[j - 1]；不等时保留原值。
  4. 扫描结束后返回 dp[t.length()]。

例如 s = "aab"、t = "ab"：dp 依次为 [1,0,0] -> [1,1,0] -> [1,2,0] -> [1,2,2]，答案为 2，对应选择下标 {0,2} 或 {1,2}。

循环不变量是：每轮结束后，dp[j] 恰好统计已扫描的 s 前缀组成 t 前 j 个字符的全部方案。转移不重不漏，归纳到完整的 s 后，dp[n] 就是答案。

代码实现

class Solution {
    public int numDistinct(String s, String t) {
        long[] dp = new long[t.length() + 1];
        dp[0] = 1;

        for (int i = 0; i < s.length(); i++) {
            int upper = Math.min(i + 1, t.length());
            for (int j = upper; j >= 1; j--) {
                if (s.charAt(i) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return (int) dp[t.length()];
    }
}

func numDistinct(s string, t string) int {
    dp := make([]int64, len(t)+1)
    dp[0] = 1

    for i := 0; i < len(s); i++ {
        upper := len(t)
        if i+1 < upper {
            upper = i + 1
        }
        for j := upper; j >= 1; j-- {
            if s[i] == t[j-1] {
                dp[j] += dp[j-1]
            }
        }
    }
    return int(dp[len(t)])
}

复杂度分析

  • 时间复杂度：$O(mn)$，其中 m、n 分别是 s、t 的长度。
  • 空间复杂度：$O(n)$，滚动数组只保留目标串这一维。

关键点总结

  • 状态统计的是下标选择方案数，而不是不同字符串的数量。
  • 转移按“使用或不使用当前 s 字符”划分，保证不重不漏。
  • dp[0] = 1 是计数 DP 的有效起点。
  • 一维压缩后必须倒序更新，避免同一字符被重复使用。
  • 计数累加使用更宽的整数类型，最后按题目返回类型转换。

易错点总结

  • 把子序列当成子串：子序列不要求连续，只要求相对顺序不变。
  • 把 dp[0] 初始化为 0：所有后续状态都会失去计数来源。
  • 正序更新 dp：s = "aa"、t = "aa" 时第二轮会重复使用当前字符，错误地得到 2，正确答案是 1。
  • 匹配时写成 dp[j] = dp[j - 1]：会丢掉“不使用当前字符”的已有方案。
  • 字符不等时清零 dp[j]：正确做法是保留旧值，因为仍可跳过当前字符。
  • 下标错位：状态长度 j 对应的末尾字符是 t[j - 1]。

相似题目

题目 难度 考察点
72. 编辑距离 中等 求最小操作次数，转移取最值且多出替换一支
392. 判断子序列 简单 只判存在性，贪心双指针即可，无需计数
583. 两个字符串的删除操作 中等 两串都可删，求最少删除步数而非方案数
792. 匹配子序列的单词数 中等 一个主串对多个模式串，重点是预处理与分桶
940. 不同的子序列 II 困难 统计本质不同的子序列，需要按末尾字符去重
1143. 最长公共子序列 中等 求公共部分的最大长度，转移取 max 而非求和
LCR 095. 最长公共子序列 中等 与 1143 同题换皮，可用来对照两种转移的写法差异
LCR 097. 不同的子序列 困难 与本题完全同题，可用于验证一维压缩写法是否可复用