题目

  1. 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, 找出S中有多少个不同的子串T, 子串是可以删除任意数量的字符(可以是0个),但是不能改变字符的顺序.

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numDistinct(string S, string T) {
        vector<vector<int> > dp(T.length() + 1, vector<int>(S.length() + 1, 0));  
        
        dp[0][0] = 1;  
        
        for (int i = 1; i < S.length() + 1; ++i)   
            dp[0][i] = 1;  
        
        for (int i = 1; i < T.length() + 1; ++i)   
            dp[i][0] = 0;  
        
        for (int i = 1; i < T.length() + 1; ++i) {  
           if (S[j - 1] == T[i - 1])  
                    dp[i][j] = dp[i][j-1]+dp[i - 1][j - 1];
           else
           {
                    dp[i][j]=dp[i][j-1];
           }
        }  
        return dp[T.length()][S.length()];  
    }  
};

思路

啊,感觉好难.

dp[i][j]是比S, T字符串长度都长1二维数组,dp[i][j] 中 i,j 表示的都是长度,不是字符串的index.

比如, dp[2][3]表示T中的ra和S中的rab的匹配情况。

(1)显然，至少有dp[i][j] = dp[i][j - 1].

比如, 因为T 中的”ra” 匹配S中的 “ra”， 所以dp[2][2] = 1 。 显然T 中的”ra” 也匹配S中的 “rab”，所以s[2][3] 至少可以等于dp[2][2]。(也就是说,S多了一个字符,dp肯定更大了)

(2) 如果T[i-1] == S[j-1]， 那么

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

前者是截止到当前字母的前一个字母一共有多少个匹配的，那当前字母相等自然这些会继续匹配；后者是截止到当前字母有多少个匹配的，那当前字母可以替换它们，于是就把二者相加即可。

比如, T中的”rab”和S中的”rab”显然匹配，

根据(1)， T中的”rab”显然匹配S中的“rabb”，所以dp[3][4] = dp[3][3] = 1，

根据(2), T中的”rab”中的b等于S中的”rab1b2”中的b2, 所以要把T中的”rab”和S中的”rab1”的匹配个数累加到当前的dp[3][4]中。 所以dp[3][4] += dp[2][3] = 2; 就是去掉S中的这个,有多少个可以匹配和加上S中的这个的匹配个数.

(3) 初始情况是
dp[0][0] = 1; // T和S都是空串.
dp[0][1 … S.length() ] = 1; // T是空串，S只有一种子序列匹配。
dp[1 … T.length() ][0] = 0; // S是空串，T不是空串，S没有子序列匹配。