leetcode115.Distinct Subsequences

发表于 更新于 分类于 ，

题目要求

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

判断S字符串中通过删减单词含有几个T字符串。例如rabbbit中含有3个rabbit字符串，通过分别删除第1，2，3个b。

思路和代码

这时一道典型的DP题。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。在这道题目中，如果我们想要计算S中含有几个T（假设S长度为n，T长度为m），那么我们只需要知道S[0...n]含有几个T[0...m-1]以及S[0...n-1]含有几个T[0...m-1]。
从中归纳出最普遍的场景，也就是如果想要计算S[0…i]含有几个T[0…j]，可以从以下两种场景来考虑：

1.S[i]!=T[j]
那么S[0...i]包含的T[0...j]的数量等价于S[0...i-1]包含T[0...j]的数量。
2.S[i]==T[j]
那么S[0...i]包含的T[0...j]的数量等价于S[0...i-1]包含T[0...j]的数量**加上**S[0...i-1]包含T[0...j-1]的数量

再来考虑初始的极端情况

1.j==0，此时S为一个空字符串，那么S的任何自字符串都包含一个唯一空字符串
2.i==0&&j！=0 此时S为非空字符串而T为空字符串，那么S包含0个T

之后我们采用int[m+1][n+1]来存储临时变量，其中int[i+1][j+1]表示S[0…j]含有几个T[0…i]
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numDistinct(String s, String t) {
    if(s==null || t==null) return 0;
    if(t.isEmpty()) return 1;
    int[][] temp = new int[t.length()+1][s.length()+1];
    for(int i = 0 ; i<s.length()+1 ; i++) temp[0][i] = 1;
    
    for(int i = 0; i<t.length() ; i++){
        for(int j = 1 ; j<s.length()+1 ; j++){
            if(t.charAt(i)==s.charAt(j-1)){
                temp[i+1][j] = temp[i+1][j-1]+ temp[i][j-1];
            }else{
                temp[i+1][j] = temp[i+1][j-1];
            }
        }
    }
    return temp[t.length()][s.length()];
}

对这段代码的优化我们可以考虑不采用二维数组而采用一维数组的方式来存储过程值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int numDistinct2(String s, String t) {
    int[] array = new int[s.length()+1];
    int prev = 1;
    for(int i = 0 ; i<s.length()+1 ; i++) array[i] = 1;
    for(int i = 0 ; i<t.length() ; i++){
        for(int j = 0 ; j<s.length()+1 ; j++){
            int temp = array[j];
            if(j==0) array[j] = 0;
            else if(t.charAt(i) == s.charAt(j-1)){
                array[j] = array[j-1]+prev; 
            }else{
                array[j] = array[j-1];
            }
            prev = temp;

        }
    }
    return array[s.length()];
}