leetcode-392：判断子序列

问题

给定字符串 s 和 t ，判断 s 是否为 t 的子序列
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

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

示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

思路

从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况
所以掌握本题也是对后面要讲解的编辑距离的题目打下基础

动态规划五部曲分析如下：

• 确定dp数组以及下标的含义

  • **dp[i][j]** 表示以下标**i-1**为结尾的字符串**s**，和以下标**j-1**为结尾的字符串**t**，相同子序列的长度为**dp[i][j]**
  • 注意这里是判断s是否为t的子序列。即t的长度是大于等于s的

• 确定递推公式

  • 在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
    • if (s[i - 1] == t[j - 1])
      • t中找到了一个字符在s中也出现了
    • if (s[i - 1] != t[j - 1])
      • 相当于t要删除元素，继续匹配
  • if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
  • if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j]的数值就是看s[i - 1]与t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

• dp数组如何初始化

  • 从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1]和dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的
  • 这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标**i-1**为结尾的字符串**s**，和以下标**j-1**为结尾的字符串**t**，相同子序列的长度为**dp[i][j]**，因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：

• 这里dp[i][0]和dp[0][j]是没有含义的，仅仅是为了给递推公式做前期铺垫，所以初始化为0
• 其实这里只初始化**dp[0][j]**就够了，但一起初始化也方便，所以就一起操作了

  int[][] dp = new int[s.length() + 1][t.length() + 1];

• 确定遍历顺序

  • 同理从从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1]和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右

• 举例推导dp数组

  • 以示例一为例，输入：s = “abc”, t = “ahbgdc”，dp状态转移图如下：

dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度，所以如果dp[s.length()][t.length()]与字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s就是t的子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                char c1 = s.charAt(i - 1);
                char c2 = t.charAt(j - 1);
                if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if (dp[s.length()][t.length()] == s.length()) return true;
        return false;
    }
}

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