Problem_115. Distinct Subsequences - xwu36/LeetCode GitHub Wiki

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.

---

Explaination:
dp[i][j] means the number of distinct subsequences of S[0, i] matches T[0, j]
Ex.
s: aaaaa
t: aa
=>
   0 1 2 3 4 5
 0 1 1 1 1 1 1
 1 0 1 2 3 4 5
 2 0 0 1 3 6 10  

s: abaaba
t: ab
=>
   0 1 2 3 4 5 6
 0 1 1 1 1 1 1 1
 1 0 1 1 2 3 3 4
 2 0 0 1 1 1 4 4 
 if(s[i] == t[j])
     dp[i][j] = dp[i - 1][j] + dp[i][j];
 else
     dp[i][j] = dp[i - 1][j];

code:

class Solution {
    public int numDistinct(String s, String t) {
        int n1 = s.length();
        int n2 = t.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for(int i = 0; i <= n1;i++)
            dp[i][0] = 1;
        for(int i = 0; i < n1; i++){
            for(int j = 0 ; j < n2; j++){
                if(s.charAt(i) == t.charAt(j))
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                else
                    dp[i + 1][j + 1] = dp[i][j + 1];
            }
        } 
        return dp[n1][n2];
    }
}