判断子序列

392. 判断子序列 - 力扣（LeetCode）

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

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

进阶：

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

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

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

示例 2：

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

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

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

dp[i] [j]：长度为[0, i - 1]的字符串s与长度为[0, j - 1]的字符串t的最长公共子序列为dp[i] [j]

为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？

这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以，我在 动态规划：718. 最长重复子数组 (opens new window)中的「拓展」里详细讲解了区别所在，其实就是简化了dp数组第一行和第一列的初始化逻辑。

确定递推公式

确定递推公式

在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

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

其实这里 大家可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的，区别就是本题如果删元素一定是字符串t，而 1143.最长公共子序列是两个字符串都可以删元素。

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        int len1 = str1.length;
        int len2 = str2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        //dp[i][j]表示以下标i-1为结尾的str1和以下标j-1为结尾的str2的最长公共子序列
        for(int i = 1; i <= len1; i ++ ){
            for(int j = 1; j <= len2; j++){
                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{ //如果不匹配，只需取删除t的最后一个字符后的最长公共子序列
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[len1][len2] == len1) return true;
        return false;

    }
}