115. 不同的子序列

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)

题目数据保证答案符合 32 位带符号整数范围。

示例 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

提示:

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

算法思路:

考虑 动态规划dp[i][j] 表示 s 中下标 0~i-1 子串的子序列中出现 t 中下标 0~j-1 子串的个数,递推公式如下:

  • 比较 s[i-1]t[j-1](i>=1,j>=1),如果相同,则包含两个部分,⼀部分是用 s[i - 1] 来匹配,那么个数为 dp[i - 1][j - 1],另⼀部分是不用 s[i - 1] 来匹配,个数为 dp[i - 1][j]。如下:

1653445450067

  • i ==0j==0时初始化如下:

    // 非空字符串中子序列为空串的个数为 1
    for (int i = 1; i <= len1; i++) dp[i][0] = 1;
    // 空串中子序列为非空字符串的个数为 0
    for (int j = 1; j <= len2; j++) dp[0][j] = 0;
    // 空串中子序列为空串的个数为 1
    dp[0][0] = 1;
    

代码实现:

class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        // dp[i][j]:s中 0~i-1 子串的子序列中出现 t中 0~j-1 子串的个数
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 非空字符串中子序列为空串的个数为 1
        for (int i = 1; i <= len1; i++) dp[i][0] = 1;
        // 空串中子序列为非空字符串的个数为 0
        for (int j = 1; j <= len2; j++) dp[0][j] = 0;
        // 空串中子序列为空串的个数为 1
        dp[0][0] = 1;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 相同,
                    // ⼀部分是⽤ s[i - 1]来匹配,那么个数为 dp[i - 1][j - 1]。
                    // ⼀部分是不⽤ s[i - 1]来匹配,个数为 dp[i - 1][j]。
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 不相同,不能⽤ s[i - 1]来匹配,个数为 dp[i - 1][j]
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

Q.E.D.


以无限为有限,以无法为有法