leetcode 115 不同的子串

发表于

题目

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:

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一样的子串数量，可以任意增减s中的元素，得到剩下的子串。

一看到字符串匹配，就会想到使用动态规划算法，那么这一题的特征是什么呢？对每一个字符都有这样的选择：如果这个字符匹配了，那么就要兼顾选择了这个字符的情况（向后继续匹配），以及没有选择这个字符的情况（没有匹配，向后移一位），具体来说就是维护两个变量i和j，i对应字符串s，j对应字符串t。

1
2
3
4
5
func
设 res = 0
若 s[i] == t[j]:
	res += func(i+1, j+1)	//匹配
res += func(i+1, j)		//默认情况

实际实现：

1
2
3
4
5
6
7
8
9
10
int dp(int i, int j, string s, string t) {
    if(j == t.size()) return 1;
    if(i == s.size()) return 0;
    int res = 0;
    if(s[i] == t[j]){
        res += dp(i + 1, j + 1, s, t);
    }
    res += dp(i + 1, j, s, t);
    return res;
}

然而，这样的算法是会超时的，原因就是它使用了递归，递归相比起来花费还是比较高。

解法二

第二种解法就不再使用递归了，而是维护一个vector，在循环中实现dp。vector的size设为字符串t的size+1，外部循环对s字符串进行遍历，内部逐步的对t中每一个字符在s中的出现次数进行累计，最后得到结果。

实际实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
int numDistinct(string s, string t) {
    vector<int> dp(t.size() + 1, 0);
    dp[0] = 1;
    for(int i = 1; i <= s.size(); ++i){
        int min_ = min(i, (int)t.size());
        for(int j = min_; j >= 1; j--){
            if(s[i - 1] == t[j - 1]){
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[t.size()];
}