115. Distinct Subsequences

Posted on | In | 浏览 次
Words count in article: 643 | Reading time ≈ 3

题目

Given a string S and a string T, count the number of distinct subsequences of Swhich 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:

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

Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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、t，计算S的不同子序列中等于T的子序列数量。
  • 一开始有点迷茫，不知道其中的转移方程是怎样的，只能举例然后观察一下其中的状态转移方程了。使用dp[i][j]记录字符串S的前i个字符的子串中有多少个与字符串T的前j个字符构成的子串相等的子序列。
  • Example 1 - S = "rabbbit", T = "rabbit"
T \ S $\emptyset$ r a b b b i t
$\emptyset$ 1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
  • Example 2 - S = "babgbag", T = "bag"
T \ S $\emptyset$ b a b g b a g
$\emptyset$ 1 1 1 1 1 1 1 1
b 0 1 1 2 2 3 3 3
a 0 0 1 1 1 1 4 4
g 0 0 0 0 1 1 1 5
  • 通过对样例的分析，我们可以得到dp[i][j] >= dp[i][j-1]在j-1>=0的条件下。同时当T为空串的时候，dp[i][0] = 1，因为空串是任一字符串的子串。再仔细观察，可以得到当s[i-1] == t[j-1]的时候，dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。综合起来，我们可以得到状态转移的表示:dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0);

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDistinct(string s, string t) {
        int dp[s.size() + 1][t.size() + 1];

        for(int i = 0; i <= s.size(); ++i) {
            dp[i][0] = 1;
        }	

        for(int j = 1; j <= t.size(); ++j) {
            dp[0][j] = 0;
        }

        for(int i = 1; i <= s.size(); ++i) {
            for(int j = 1; j <= t.size(); ++j) {
                dp[i][j] = dp[i-1][j] + (s[i-1] == t[j-1] ? dp[i-1][j-1] : 0);
            }
        }

        return dp[s.size()][t.size()];
    }
};