第九章 动态规划 part15（编辑距离专题） 392. 判断子序列 115. 不同的子序列

第五十七天| 第九章 动态规划 part15（编辑距离专题） 392. 判断子序列 115. 不同的子序列

一、392. 判断子序列

• 题目链接：https://leetcode.cn/problems/is-subsequence/

• 题目介绍：

  • 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

    字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

    示例 1：

    输入：s = "abc", t = "ahbgdc"
    输出：true
    1
    2

• 思路：

  • （1）确定dp数组及下标含义：

    • dp[i][j]：表示的是以下标i-1为结尾的char1和以下标j-1为结尾的char2的公共子序列的长度
      1

  • （2）确定递推公式:

    • 第一种情况：char1[i-1] == char2[j-1]

      • dp[i][j] = dp[i-1][j-1] + 1;
        1

    • 第二种情况：char1[i-1] != char2[j-1]

      • 如果, 因此判断s是否是t的子序列，只能由t来删除元素char2[j-1](这里就体现了编辑距离的思想，但这里涉及的还只是删除元素)，因此比较的就是char1[0, i-1]和char2[0, j-2]，即dp[i][j] = dp[i][j-1];
        1

  • （3）初始化dp数组：

    • 全部初始化为0，主要是dp[i][0]和dp[0][j]没有意义，因此初始化为0，其余的都可以覆盖所以也要初始化为0即可。
      1

  • （4）遍历顺序：正序

• 代码：

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] char1 = s.toCharArray();
        char[] char2 = t.toCharArray();
        // （1）确定dp数组及下标含义
        // dp[i][j]：表示的是以下标i-1为结尾的char1和以下标j-1为结尾的char2的公共子序列的长度
        int[][] dp = new int[char1.length + 1][char2.length + 1];
        // （3）初始化dp数组：
        // 全部初始化为0，主要是dp[i][0]和dp[0][j]没有意义，因此初始化为0，其余的都可以覆盖所以也要初始化为0即可。
        // （4）遍历顺序：正序
        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                // （2）确定递推公式
                // 如果char1[i-1] == char2[j-1], dp[i][j] = dp[i-1][j-1] + 1
                // 如果char1[i-1] != char2[j-1], 因此判断s是否是t的子序列，只能由t来删除元素char2[j-1](这里就体现了编辑距离的思想，但这里涉及的还只是删除元素)，因此比较的就是char1[0, i-1]和char2[0, j-2]，即dp[i][j] = dp[i][j-1];
                if (char1[i-1] == char2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if (dp[char1.length][char2.length] == s.length()) {
            return true;
        } else {
            return false;
        }
    }
}
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

二、115. 不同的子序列

• 题目链接：https://leetcode.cn/problems/distinct-subsequences/

• 题目介绍：

  • 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

    示例 1：

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

• 思路：

  • （1）确定dp数组及下标的含义：

    • dp[i][j]：表示的是以下标i-1为结尾的char1中出现以下标j-1为结尾的char2的个数
      1

  • （2）确定递推公式：

    • 递推公式是最难理解的一个部分，在编辑距离类的题目中，递推公式的推到一般分为两种情况，一种是s[i-1] == t[j-1]， 另一种是s[i-1] != t[j-1]

    • 情况一：s[i-1] == t[j-1]

      • 情况一的第一种可能：利用s[i-1]

        • 意味着这两个字符串的当前下标的值是相等的，也就是说可以不比较最后一位，即dp[i-1][j-1]
          1

      • 情况一的第二种可能：不利用s[i-1]

      • 也就是说删除s[i-1]，也可能包含以下标j-1为结尾的t，即dp[i-1][j]
        1

      • 例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

      • 所以dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        1

    • 情况二：s[i-1] != t[j-1]

      • 如果当前下标s和t不相等，只能删除s的元素，因为要判断的是s中有多少个t，即dp[i][j] = dp[i-1][j];
        1

• 代码：

class Solution {
    public int numDistinct(String s, String t) {
        char[] char1 = s.toCharArray();
        char[] char2 = t.toCharArray();
        // （1）确定dp数组及下标的含义
        // dp[i][j]：表示的是以下标i-1为结尾的char1中出现以下标j-1为结尾的char2的个数
        int[][] dp = new int[char1.length+1][char2.length+1];
        // （3）初始化dp数组：
        // 这个是第二难理解的点
        // 和以往不同，以往dp数组的第一行的第一列都是没有意义的，但是本题不一样
        // 对于第一列，即dp[i][0]，表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
        // dp[i][0] = 1;即，把s的所有元素删除，得到的就是空串，这就是一种匹配方式
        // 对于第一行，即dp[0][j]，通俗一点理解就是s为空串，t不是，所以dp[0][j] = 0。但是dp[0][0]它是有意义的，即空串和空串匹配为一种方式，因此dp[0][0] = 1;
        for (int i = 0; i <= char1.length; i++) {
            dp[i][0] = 1;
        }
        // （4）确定遍历顺序
        // 正序
        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                // （2）确定递推公式
                // 递推公式是最难理解的一个部分：
                // 在编辑距离类的题目中，递推公式的推到一般分为两种情况，一种是s[i-1] == t[j-1]， 另一种是s[i-1] != t[j-1]
                // 2.1 s[i-1] == t[j-1]
                // 第一种可能：利用s[i-1]，意味着这两个字符串的当前下标的值是相等的，也就是说可以不比较最后一位，即dp[i-1][j-1]
                // 还有一种可能：不利用s[i-1]，也就是说删除s[i-1]，也可能包含以下标j-1为结尾的t，即dp[i-1][j]
                // 所以dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                // 2.2 s[i-1] != t[j-1]
                // 如果当前下标s和t不相等，只能删除s的元素，因为要判断的是s中有多少个t，即dp[i][j] = dp[i-1][j];
                if (char1[i-1] == char2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        // 只要是由上方或者左方，即不只有左上角可以推出最终结果的题，它的最终结果都在dp数组的右下角
        return dp[char1.length][char2.length];
    }
}
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