题目

the leetcode link

  1. 不同的子序列
    给定一个字符串 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 由英文字母组成

解题思路

  1. s, t引入头部””空字符；定义m、n分别是s、t长度，定义二维数组dp[m+1][n+1]，值表示s[0：i]可以组成t[0：j]的子序列最大数量；
    （i，j泛指符合题目不超边界的相关变量，[0：i]表示枚举从0到i）
  2. 初始化
  • s[0：i]全部删除取得子序列“”，成功组成t[0]即“” ，所以dp[0：m][0] = 1
  • s[0]是“”，无法组成非“”字符串t[1：i] ，所以dp[0][1：n] = 0，默认已初始化
  1. 递推过程
  • 结尾字符相等，取两种情况的结合
    第一种，用到s[i-1]的结尾字符，则数量与dp[i-1][j-1]相等
    第二种，不用到s[i-1]的结尾字符，则数量与dp[i-1][j]相等
  • 结尾字符不相等，不用到s[i-1]的结尾字符, 则等于dp[i-1][j]
    tips：由于引入“”的关系，s的当前字符指针是i-1，t的当前字符指针是j-1，与dp的i-1，j-1区别开
  1. 剪枝优化，限制t[0：j]长度不可能大于s[0：i]
  2. 返回结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m+1][n+1];
        //s[0：i]全部删除取得子序列“”，成功组成t[0]“” ，所以dp[0：m][0] = 1
        //s[0]是“”，无法组成非“”字符串t[1：i] ，所以dp[0][1：n] = 0，默认已初始化
        for(int i=0;i<=m;i++){
            dp[i][0] = 1;
        }


        for(int i=1;i<=m;i++){
            for(int j=1;j<=Math.min(i,n);j++){ // 剪枝操作，t[0：j]长度不可能大于s[0：i]

                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[m][n];
    }
}