Distinct Subsequences

Question

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

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Thoughts

dp[i][j]表示S前i个与T前j个的distinct subsequences number

init state

dp[0][j] = 0 dp[i][0] = 1 (问清楚这个应该是多少)

connection function

如果S[i-1] == T[j-1], 那么既有dp[i-1][j-1]的数量(直接加上S最后的char)，也有dp[i-1][j]的数量（不用这个S的char），

if S[i-1] == T[j-1]:
    dp[i][j] = dp[i-1][i-1] + dp[i-1][j]
else:
    dp[i][j] = dp[i-1][j-1]

final result

dp[len(S)][len(T)]

Solution

class Solution: 
    # @param S, T: Two string.
    # @return: Count the number of distinct subsequences
    def numDistinct(self, S, T):
        # write your code here
        if not S:
            return 0
        if not T:       
            return 1  
        dp = [[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
        for j in range(len(T)+1):
            dp[0][j] = 0
        for i in range(len(S)+1):
            dp[i][0] = 1

        for i in range(1, len(S)+1):  
            for j in range(1, len(T)+1):                         
                    if S[i-1] == T[j-1]:                        
                        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]  
                    else:        
                        dp[i][j] = dp[i-1][j] 
        return dp[len(S)][len(T)]