LeetCode: Distinct Subsequences

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.

---

We can use dynamic programming to solve this problem. Let dp[i] be the number of ways to match T[i:] in S. Then we start from the end of S string and check backwards, if S[j] == T[i], dp[i] += dp[i+1]. Let's take an example:

S: rabbbitt; T: rabbit ; Si = 7; dp:[0, 0, 0, 0, 0, 1, 1]

S: rabbbitt; T: rabbit ; Si = 6; dp:[0, 0, 0, 0, 0, 2, 1]

S: rabbbitt; T: rabbit ; Si = 5; dp:[0, 0, 0, 0, 2, 2, 1]

S: rabbbitt; T: rabbit ; Si = 4; dp:[0, 0, 0, 2, 2, 2, 1]

S: rabbbitt; T: rabbit ; Si = 3; dp:[0, 0, 2, 4, 2, 2, 1]

S: rabbbitt; T: rabbit ; Si = 2; dp:[0, 0, 6, 6, 2, 2, 1]

S: rabbbitt; T: rabbit ; Si = 1; dp:[0, 6, 6, 6, 2, 2, 1]

S: rabbbitt; T: rabbit ; Si = 0; dp:[6, 6, 6, 6, 2, 2, 1]

C++ Code:

/*
 * func: distinct_sequence
 * goal: count the number of distinct subsequences of T in S
 * @param S: source string
 * @param T: target string
 * return: total number
 */
/*
 * using DP: dp_helper[i] means the number of ways to match until the ith char in T
 * complexity: time O(ST), space O(T)
 */
int distinct_sequence(string S, string T){
    vector<int> dp_helper(T.size() + 1);
    dp_helper[T.size()] = 1;
    for(int i = S.size()-1; i >= 0; --i){
        for(int j = 0; j < T.size(); ++j){
            if(S[i] == T[j])
                dp_helper[j] += dp_helper[j+1];
        }
    }
    return dp_helper[0];
}

Python Code:

# func: count the number of distinct subsequences of T in S
# @param S: source string
# @param T: target string
# @return: total count
def distinct_subsequence(S, T):
    dp_helper = [0] * (len(T)+1)
    dp_helper[-1] = 1
    for i in xrange(len(S)-1, -1, -1):
        for j in xrange(len(T)):
            if S[i] == T[j]:
                dp_helper[j] += dp_helper[j+1]
    return dp_helper[0]