115. 不同的子序列

题目描述 distinct-subsequences

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

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

题目理解

• S “” 是“a”，“ab”，“abc”的个子序列吗 ？ 个数 1
• S 字符串"b" 在T字符串“bab”出现的个数? 2
• S 字符串"b" 在T字符串“babab”出现的个数? 3
• S 字符串"ba" 是T字符串“b”子序列吗 ？ 肯定不是 怎么删除都不可能呀

根据定义跟删除字符个数没关系 删除后的结果s和t相等就可以
好像发现一个规律 只要字符串不相等 你包含再多字符也没用

image.png

code

class Solution {
    public int numDistinct(String s, String t) {
          // array creation
    int[][] mem = new int[t.length()+1][s.length()+1];

    // filling the first row: with 1s
    for(int j=0; j<=s.length(); j++) {
        mem[0][j] = 1;
    }
    
    // the first column is 0 by default in every other rows but the first, which we need.
    
    for(int i=0; i<t.length(); i++) {
        for(int j=0; j<s.length(); j++) {
            if(t.charAt(i) == s.charAt(j)) {
                mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
            } else {
                mem[i+1][j+1] = mem[i+1][j];
            }
        }
    }
    
    return mem[t.length()][s.length()];
    }
}