力扣115题Java

题目

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

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

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

代码

class Solution {

   public int numDistinct(String s, String t) {

       int n = s.length(), m = t.length();

       if (n < m)//s长度小于t，个数为0

           return 0;

       char[] cs = s.toCharArray(), ct = t.toCharArray();

       int[][] dp = new int[n + 1][m + 1];//s[i,n]子序列中t[j,m]子串出现的个数

       for (int i = 0; i <= n; i++) {

           for (int j = 0; j <= m; j++)

               dp[i][j] = 0;

           dp[i][m] = 1;//s对空字符串都有1种取法

       }

       for (int i = n - 1; i >= 0; i--) {

           int range = Math.max(0, m - n + i);//剪枝j的取值范围

           for (int j = m - 1; j >= range; j--) {

               dp[i][j] = dp[i + 1][j];//不选取i的情况

               if (cs[i] == ct[j]) //选取i的情况

                   dp[i][j] += dp[i + 1][j + 1];

           }

       }

       return dp[0][0];

   }

}