115. Distinct Subsequences

Link

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

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

Solution

很神奇的使用DP，

建立二微陣列dp[][], 其中dp[i][j] 表示s取前面i個 跟t取前面j個，能夠形成等於t的組合數, i介於(0 到 s.length()) j介於(0 到 t.length()) 所以:

int[][] dp = new int[s.length()+1][t.length()+1];

其中若i = 0，表示s為空字串，那必定沒可能有組合數。 dp[0][j] = 0 , for all j

其中若j = 0，表示t為空字串，那必定組合數都有一個。 dp[i][0] = 1 , for all i dp[0][0] = 1，都是s, t空字串，組合數為1

        for(int j = 0; j< t.length()+1; j++){
            dp[0][j] = 0; //s is empty string
        }
        for(int i = 0; i < s.length()+1; i++){
            dp[i][0] = 1; //t is empty string
        }

接下來要推廣dp[i][j]的值 先考慮s.charAt(i) != t.charAt(j)的狀況，表示s新進的元素，不可能形成組合數，那麼有沒有放入s[i]都是一樣的。所以此狀況下組和數等於dp[i-1][j] 反之，若是相等，那接下來就會有兩種可能，一種是仍無法形成組合數 dp[i-1][j] 另一種為行程組合數，此時組合數的個數會跟s, t各少掉一個元素是一樣的: dp[i-1][j-1]

最後算出dp[s.length][t.length]即為解

 public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length()+1][t.length()+1];
        for(int i = 0; i< t.length()+1; i++){
            dp[0][i] = 0; //s is empty string
        }
        for(int j = 0; j < s.length()+1; j++){
            dp[j][0] = 1; //t is empty string
        }
        
        for(int i = 1; i < s.length()+1; i++){
            for(int j = 1; j < t.length()+1; j++){
                if(t.charAt(j-1) == s.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];  
                    // two case: 
                    // 1. have a match : dp[i-1][j-1]
                    // 2. without a match : dp[i-1][j]
                }
                else{
                    dp[i][j] = dp[i-1][j]; // will same as exlude the s.charAt[i]
                }
            }
        }
        
        return dp[s.length()][t.length()];
    }