• 不同的子序列

    Category Difficulty Likes Dislikes
    algorithms Hard (52.29%) 861 -
    Tags

    string | dynamic-programming

    Companies

    Unknown

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

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

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

    示例 1：

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

    示例 2：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入：s = "babgbag", t = "bag"
    输出：5
    解释：
    如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
    babgbag
    babgbag
    babgbag
    babgbag
    babgbag

    提示：

    • 0 <= s.length, t.length <= 1000
    • s 和 t 由英文字母组成

代码

动态规划(c++)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * @lc app=leetcode.cn id=115 lang=cpp
 *
 * [115] 不同的子序列
 */

// @lc code=start
class Solution {
public:
    int numDistinct(string s, string t) {
        int s_len = s.size(), t_len = t.size();
        vector<vector<unsigned long long>> dp(s_len+1, vector<unsigned long long>(t_len+1, 0));

        /** 
         * t是s的子集，t[0]时为空字符串，空字符串是任何字符的子集。
         */
        for (int i = 0; i < s_len+1; ++i) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < s_len; ++i) {
            for (int j = 0; j < t_len; ++j) {
                /** 
                 * 字符相等，dp[i][j]是i和j都往下走，dp[i][j+1]是i往下走，j原地
                 * 字符不相等，i往下走，值等于dp[i][j+1]
                 */
                /** 
                 *     s = rabbbit, t = rabbit;
                 *     1 0 0 0 0 0 0
                 *     1 1 0 0 0 0 0
                 *     1 1 1 0 0 0 0
                 *     1 1 1 1 1 0 0
                 *     1 1 1 2 2 0 0
                 *     1 1 1 2 3 0 0
                 *     1 1 1 2 3 3 0
                 *     1 1 1 2 3 3 3
                 * the finally val is dp[s_len][t_len] = 3;
                 */
                if (s[i] == t[j]) {
                    dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
                } else {
                    dp[i+1][j+1] = dp[i][j+1];
                }
            }
        }
        return dp[s_len][t_len];
    }
};
// @lc code=end