Distinct Subsequences

Problem Description

Given a string S and a string T, count the number of distinct sub-sequences of T in S.

A sub-sequence 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.

NOTE: The above problem statement is not very clear. We can make it "cleaner" by re-stating the problem as:
Given a string S and a string T, counting the number of ways that we remove some (or none) characters in S to get the remaining string equal to T.

Solutions

For a string str, we denote str[0,j] is the sub-string of str from index 0 to j inclusively. We easily guess that this solution can be solved by Dynamic Programming.
If we call dp[i][j] is the number of ways to remove some characters from S[0,i] to get T[0,j], we have the recursive formula:
dp [i][j] = dp[i-1][j] if S[i] != T[j] , or
dp [i][j] = dp[i-1][j] + dp[i-1][j-1] if S[i] ==T[j]

Therefore, we can come up with solution I), and improve it on II).

I. O(m*n) space

public class Solution {
    public int numDistinct(String s, String t) {
        if(s.length()==0 || s == null || t == null || t.length() == 0) return 0;
        int[][] dp = new int[s.length()][t.length()];
        
        char c = t.charAt(0);
        for(int i=0; i<s.length(); i++){
            dp[i][0] = (i==0? 0: dp[i-1][0]) + (s.charAt(i)==c?1:0);
        }
        for(int i = 1; i<s.length(); i++){
            c = s.charAt(i);
            for(int j=1; j<t.length(); j++){
                dp[i][j] = dp[i-1][j] + (t.charAt(j)==c?dp[i-1][j-1]:0);
            }
        }
        return dp[s.length()-1][t.length()-1];
    }
}

II. O(n) space where n is length of T
We see that the formula of dp[i][j] refer to only dp[i-1][j] and dp[i-1][j-1]. This gives us the idea that we can reduce the space to O(n).
Since we need to make use of dp[i-1][j-1], we run backward!!!

public class Solution {
    public int numDistinct(String s, String t) {
        if(s == null || t == null || t.length() == 0) return 0;
        int[] dp = new int[t.length()];
        
        for(int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            for(int j=dp.length-1; j>=0; j--){
                if(c == t.charAt(j)){
                    dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
                }
            }
        }
        return dp[t.length()-1];
    }
}