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

It’s guaranteed the answer fits on a 32-bit signed integer.

Example 1:

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

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

---

这问题描述不清，题目想问S中有多少个不同的subsequence等于T，这里的不同是指形成subsequence的方法不同，比如样例中，rabbbit可以去掉中间任意一个b都能形成T，所以不同的方法有3种。 这是典型的动态规划问题。假设dp[i][j]表示由S[1,…,i]变到T[1,…,j]有多少种subsequence方法。此时我们有两种选择，如果S[i]!=T[j]，则等价于由S[1,…,i-1]变到T[1,…,j]，所以dp[i][j]=dp[i-1][j]；如果S[i]==T[j]，则还可以由S[1,…,i-1]变到T[1,…,j-1]，所以dp[i][j]+=dp[i-1][j-1]。
DP转移公式如下：
$$dp[i][j]=\begin{cases}dp[i-1][j] & \text{if $S[i]\neq T[j]$}\\dp[i-1][j]+dp[i-1][j-1] & \text{if $S[i]=T[j]$}\\\end{cases}$$
为了便于理解，我们先在s和t的开头添加一个哨兵字符’^’，初始值dp[i][0]=1，因为由任意字符串转换为空字符串只有一种方法，就是把s中的字符全删了；dp[0][j]=0，因为空字符串的subsequence不可能是是某个非空字符串。
完整代码如下：

class Solution {
public:
    int numDistinct(string s, string t)
    {
        if (s == "")
            return 0;
        if (t == "")
            return 1;
        s = "^" + s;
        t = "^" + t;
        int n = s.size(), m = t.size();
        vector<vector<int> > dp(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++)
            dp[i][0] = 1; // ‘*’ -> ” 1 sub
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = dp[i – 1][j];
                if (s[i] == t[j])
                    dp[i][j] += dp[i – 1][j – 1];
            }
        }
        return dp[n – 1][m – 1];
    }
};

本代码提交AC，用时20MS。

二刷。不添加哨兵，vector增加1也是可以的，代码如下：

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        if(n > m) return 0;
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
        for(int i = 0; i < m; ++i) dp[i][0] = 1;
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                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[m][n];
    }
};

本代码提交AC，用时20MS。