Distinct Subsequences 118

Question

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).

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Solution

ds[i][j]表示T的前j个字符能够在S的前i个字符中能够取的子字符串的数量。

初始化：

ds[i][0]=1，即T的前0个字符总是能够成为S的一个子字符串
ds[0][j]=0(j>0)，即不可能有非空字符串是S的前0个字符的子字符串

状态函数：

如果S.charAt(i-1)==T.charAt(j-1)：
ds[i][j]=ds[i-1][j]+ds[i-1][j-1]
否则：
ds[i][j]=ds[i-1][j]

即对于S的第i位字符有两种情况：第一种为不能和T的j位字符匹配，则其值为S的前i－1位字符和T的前j位字符的匹配数；第二种情况为可以和T的第j位字符匹配，则其值为S的前i－1位字符和T的前j位字符的匹配数＋S的前i－1位字符和T的前j－1位字符的匹配数。

代码如下：

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        // write your code here
        if(S == null || T == null){
            return 0;
        }

        int n = S.length();
        int m = T.length();
        int[][] ds = new int[n + 1][m + 1];

        for(int i = 0; i <= n; i++){
            ds[i][0] = 1;
        }

        for(int j = 1; j <= m; j++){
            ds[0][j] = 0;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                ds[i][j] = ds[i - 1][j];
                if(S.charAt(i - 1) == T.charAt(j - 1)){
                    ds[i][j] += ds[i - 1][j - 1];
                }
            }
        }

        return ds[n][m];
    }
}