115_不同的子序列

发表于 分类于 ， 阅读次数： Waline： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

[[toc]]

115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例2:

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案,
babgbag
babgbag
babgbag
babgbag
babgbag

思路：

我们需要计算s中有多少个t，实际上就是穷举，那么我们需要考虑能不能把愿问题分解为规模更小的子问题，然后再根据子问题推导出愿问题的结果。 首先，我们可以定义这样一个dp函数： 

1
2
// 定义：s[i..] 的子序列中 t[j..]出现的次数为 dp(s,i,t,j)
int dp(string s, int i, string t, int j)
那么我们想要的结果就为dp(s, 0, t, 0)
base case为： * 1. 全部匹配完成，j == t.size() * 2. s[i..]比t[j..]还短，那么必然不可能匹配

至此，我们可以写出大概的算法框架： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int numDecodings(string s, string t) {
    return dp(s, 0, t, 0);
}

int dp(string s, int i, string t, int j) {
    // base case 1, 全部匹配完成
    if(j == t.size()) {
        return 1;
    }
    // base case 2, s[i..]的长度比t[j..]的长度短，匹配失败
    if(s.size() - i < t.size() - j) {
        return 0;
    }
    // ...
}

现在我们需要考虑如何将大问题分解为小问题，即如何求出状态转移方程。

有两种思路，第一种就是从t的角度进行思考，第二种是从s的角度进行思考。

角度一：从t的角度

我们的问题是求s[i..]的所有子序列中t[j..]出现的次数，那么我们肯定是先判断t[0]在s中出现的位置。 假如s[2],s[6]是字符t[0]，那么原问题就转化为在s[2..] ,s[6..]的所有子序列中计算t[1..]出现的次数。

1
2
3
4
5
6
7
8
9
10
11
int dp(string s, int i, string t, int j) {
    int res = 0;
    // 在s[i..]中寻找 k,使得 s[k] == t[j]
    for(int k = i; k < s.size(); k++) {
        if(s[k] == t[j]) {
            // 累加结果
            res += dp(s, k + 1, t, j + 1);
        }
    }
    return res;
}

最后我们只需要加上备忘录消除重叠子问题即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int> > memo;
    int numDistinct(string s, string t) {
        memo.resize(s.size(), vector<int>(t.size(), -1));
        return dp(s, 0, t, 0);
    }
    // 定义：s[i...] 的子序列中 t[j...]出现的次数为dp(s, i, t, j)
    int dp(string s, int i, string t, int j) {
        // base case 1
        if(j == t.size()) {
            return 1;
        }
        // base case 2
        if(s.size() - i < t.size() - j) {
            return 0;
        }
        if(memo[i][j] != -1) {
            return memo[i][j];
        }
        int res = 0;
        // 状态转移方程
        // 在 s[i..]中寻找k,使得s[k] == t[j]
        for(int k = i; k < s.size(); k++) {
            if(s[k] == t[j]) {
                res += dp(s, k + 1, t, j + 1);
            }
        }
        memo[i][j] = res;
        return res;
    }
};

时间复杂度：O(m*n) * O(m)

m表示s的长度，n为t的长度。 子问题的个数 * 函数本身的时间复杂度

角度二：从s的监督

我们的问题是计算s[0..]的所有子序列中t[0..]出现的次数，那么我们可以先看下s[0]是否能匹配t[0], 如果不匹配，那么愿问题就可以转化为计算s[1..]的所有子序列中t[0..]出现的次数。 如果匹配，那么有以下两种情况，这两种情况是累加的关系： * 1. 让s[0]匹配t[0]，那么原问题转化为在s[1..]的所有子序列中计算t[1..]出现的次数。 * 2. 不让s[0]匹配t[0]，那么原问题转化为在s[1..]的所有子序列中计算t[0..]出现的次数。

那么状态转移方程为： 

1
2
3
4
5
6
7
8
9
int dp(string s, int i, string t, int j) {
    if(s[i] == t[j]) {
        // 匹配，两种情况
        return dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);
    }else {
        // 不匹配
        return dp(s, i + 1, t, j);
    }
}

加上备忘录，代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int> > memo;
    int numDistinct(string s, string t) {
        memo.resize(s.size(), vector<int>(t.size() , -1));
        return dp(s, 0, t, 0);
    }
    int dp(string s, int i, string t, int j) {
        // base case 1
        if(j == t.size()) {
            return 1;
        }
        // base case 2
        if(s.size() - i < t.size() - j) {
            return 0;
        }

        if(memo[i][j] != -1) {
            return memo[i][j];
        }
        int res = 0;
        // 状态转移方程
        if(s[i] == t[j]) {
            res += dp(s, i + 1, t, j + 1) + dp(s, i + 1, t, j);
        }else {
            res += dp(s, i + 1, t, j);
        }
        // 将结果存入备忘录
        memo[i][j] = res;
        return res;
    }
};

时间复杂度为：O(mn)