README_CN.md

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10⁹ + 7 取模。

示例 1:

输入: s = "rabbbit", t = "rabbit"
输出: 3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2:

输入: s = "babgbag", t = "bag"
输出: 5
解释:
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

提示:

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

题解 (Rust)

1. 题解

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let mut dp = vec![vec![0; t.len()]; s.len()];

        for i in 0..s.len() {
            for j in 0..t.len().min(i + 1) {
                if i > 0 {
                    dp[i][j] = dp[i - 1][j];
                }
                if s[i] == t[j] {
                    if j == 0 {
                        dp[i][j] += 1;
                    } else {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % 1_000_000_007;
                    }
                }
            }
        }

        dp[s.len() - 1][t.len() - 1]
    }
}