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

一、392. 判断子序列

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

• 题目介绍：

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

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

    示例 1：

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

• 思路：

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

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

  • （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];
        

  • （3）初始化dp数组：

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

  • （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;}}
}

二、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）确定dp数组及下标的含义：

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

  • （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]
          

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

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

      • 例如： 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];
        

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

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

• 代码：

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];}
}