[leetcode-115]Distinct Subsequences(java)

問題描述：

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.

分析：這個問題問的實在不清楚，實際上是問s中有多少個子序列等于t。

那這個題看上去非常像0、1背包問題，對于字元串中的每一個字元都有兩種選擇，1是選，1是不選。另外遞歸+剪枝構成如下代碼，結果TLE

代碼如下：TLE

public class Solution {
    int count = ;
    int depth;
    String t;
    int tlen;
    public int numDistinct(String s, String t) {
        StringBuilder builder = new StringBuilder();
        depth = s.length();
        this.t = t;
        tlen = t.length();
        solve(s, ,builder);
        return count;
    }
      private void solve(String s,int level,StringBuilder builder){
        if(level == depth){
            return;
        }
        char ch = s.charAt(level);
        builder.append(ch);
        int size = builder.length();
        if(size<=tlen && ch == t.charAt(size-)) {
            if(size==tlen) {
                count++;
            }
            solve(s, level + , builder);
        }
        builder.deleteCharAt(size-);
        solve(s,level+,builder);
    }
}
           

然後想到是不是可以用DP算法。

令字元串s的長度為slen，令字元串t的長度為tlen，那麼最後的問題是slen的s中删除若個字元可否變成tlen的t，有幾種？

那麼子問題就是長度為i的s的子串可否變成長度為j的t的子串？有幾種。

那麼遞推關系式就變成了

dp[i][j] = chars[i]==chars[j]?dp[i-1][j-1]+dp[i-1][j] : dp[i-1][j];

于是代碼如下：300ms

public class Solution {
    public int numDistinct(String s, String t) {
        int row = s.length();
        int col = t.length();
        if(row<= || col<=)
            return ;

        int[][] dp = new int[row][col];
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();

        dp[][] = chars[]==chart[]?:;//init first row
        //init first col
        for(int i = ;i<row;i++){
            dp[i][] = dp[i-][];
            if(chars[i] == chart[])
                dp[i][] += ;
        }
        for(int i = ;i<row;i++){
            for(int j = ;j<col;j++){
                dp[i][j] = dp[i-][j];
                if(chars[i]==chart[j])
                    dp[i][j] += dp[i-][j-];
            }
        }
        return dp[row-][col-];
    }
}