distinct subsequences

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
2
3
4
5
6
7
8
9
10
11
12
13

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
^^^ ^^^

这个问题想了两个思路，但是差别不大，首先最直观的DP解法是分解为S[0…i]与T[0…j]的子问题，这样就能通过一个m*n的二维表格实现求解，当然可以优化空间为 O(m)

第二个思路是在第i遍，统计S中匹配T[0…i],切以T[i]结尾的可能，最后的总可能是将最后一行数字加起来。

• Sol 1
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  class { public: int numDistinct(string s, string t) { int n=s.size(),m=t.size(); int dp[n+1][m+1]; memset(dp,0,sizeof(dp)); for(int i=0;i<=n;i++)dp[i][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; if(s[i-1]==t[j-1])dp[i][j]+=(dp[i-1][j-1]); } } return dp[n][m]; } };

-Sol 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class :
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        ls, lt = len(s), len(t)
        res = [[0]*ls for i in range(lt)]
        for j in range(ls):
            if t[0] == s[j]:
                res[0][j] = 1
        for i in range(1,lt):
            cur = 0
            for j in range(ls):
                if j > 0:
                    cur += res[i-1][j-1]
                if t[i] == s[j]:
                    res[i][j] = cur
        return sum(res[-1])