LeetCode - Distinct Subsequences

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

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.

思路：

F[0][0] = 1; // T和S都是空串.

F[0][j] = 0; // S是空串，T只有一种子序列匹配。

F[i][0] = 1; // T是空串，S不是空串。空串是任何字符串的子序列，所以赋值为1 

F[i][j] = F[i-1][j] + (S[i-1] == T[j-1] ? F[i-1][j-1] : 0)

其中，1 <= i <= S.length, 1 <= j <= T.length

 

Solution:

public int numDistinct(String S, String T) {
    int m = S.length();
    int n = T.length();
    int[][] f = new int[m+1][n+1];
    for(int i=0; i<=m; i++) {
        f[i][0] = 1;
    }
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            if(S.charAt(i-1)==T.charAt(j-1)) {
                f[i][j] = f[i-1][j-1]+f[i-1][j];
            } else {
                f[i][j] = f[i-1][j];
            }
        }
    }
    return f[m][n];
}

 

DP的数组可以由2维降为1维。

Solution2:

int numDistinct(string S, string T) {
    vector<int> f(T.size()+1);
    //set the last size to 1.
    f[T.size()]=1;

    for(int i=S.size()-1; i>=0; --i){
        for(int j=0; j<T.size(); ++j){
            f[j] += (S[i]==T[j])*f[j+1];
        }
    }
    return f[0];
}

具体解释在这里：

http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation