题目描述

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

算法1

DP $O(m x n)$

C++ 代码

    // f[i][j] : S取前i个char，T取前j个char，即 s[0..i-1], t[0..j-1], 有多少个解
    // f[i][j] = if s[i-1]==t[j-1]: f[i-1][j-1] + f[i-1][j]; 分别是用s[i-1]和不用s[i-1]
    //           else: f[i-1][j]
    // i = 0..m, j = 0..n

    // init: f[0][0] = 1; 都为空
    //      f[i][0] = 1; t为空，s一个都不取，1种子串
    //      f[0][j] = 0; s为空，没有子串

    int numDistinct(string s, string t) {
        if(s.size() < t.size()) return 0;
        if(s.size() == t.size()) return s==t? 1:0;

        int m=s.size(), n=t.size();
        vector<vector<long long>> f(m+1, vector<long long>(n+1, 0));

        f[0][0] = 1;
        for(int i=1; i<=m; i++) f[i][0] = 1;

        // for(int j=1; j<=n; j++) f[0][j] = 0; // 已经初始化为0，无需再初始化一次

        for(int i=1; i<=m; i++) {
            int maxj = min(i, n); // no subseq if j>i
            for(int j=1; j <= maxj; j++) {
                if(s[i-1]==t[j-1]) f[i][j] = f[i-1][j-1] + f[i-1][j];
                else f[i][j] = f[i-1][j];
            }
        }

        return f[m][n];
    }