Distinct Subsequences

https://leetcode.com/problems/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:

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

Thoughts

找S中等于T的subsequence数目。subseq match想DP。action为是否让当前的S[i -1] match T[j - 1]。dp[i, j]代表S前i和T前j个有多少个匹配的子序列。dp[i][j]至少有dp[i-1][j]个，如果让S[i- 1] match T[j - 1]还有额外dp[i-1][j-1]个。由于只与上一层有关，可以只用一维空间。

Code

/*
 * @lc app=leetcode id=115 lang=cpp
 *
 * [115] Distinct Subsequences
 */
class Solution {
public:
    int numDistinct(string s, string t) {
         const int M = s.size(), N = t.size();
         vector<long> dp(vector<long>(N + 1));
         dp[0] = 1;
         for (int i = 1; i <= M; ++i) {
             for (int j = N; j >= 1; --j) {
                 if (s[i - 1] == t[j - 1]) {
                     dp[j] += dp[j - 1];
                 } 
             }
         }
         return dp[N];
    }
};

Analysis

TC: O(mn)