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

提示：

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

解法

1. 双指针

一个指针指向 s，另一个指向 t，依次判断对应元素是否相等即可。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

2. 动态规划

双指针的做法时间复杂度为 \(O(n+m)\)，其中在字符串 t 中指针存在大量无效匹配，尤其是 t 比较长的时候会更明显，是否可以在匹配到 t 的一个元素后跳过中间不匹配的元素直接达到下一位匹配元素。为此需要对 t 进行一下预处理，需要知道每个字符在某一位置后第一次出现的位置，这样就可以直接跳过中间元素。

设 dp[i][j] 为在 i 位置后字符 j （使用j + 'a'可以直接计算出字符j对应元素）第一次出现的位置，则状态转移方程为： \(dp[i][j] = \left\{ \begin{aligned} &i, & t[i] = j\\ &dp[i+1][j], & t[i] \neq j \end{aligned} \right.\)

3. 最长子序列

设 dp[i][j] 为以 s[i] 结尾和 t[j] 结尾的最长公共子序列长度。

与 1143. 最长公共子序列 相同，只不过 1143. 最长公共子序列 这里可以理解为两个字符串都能编辑，而本题只能编辑第二个字符串。

状态转移方程为： \(dp[i][j] = \left\{ \begin{aligned} & dp[i-1][j-1] + 1, & s[i - 1] = t[j - 1] & \\ & dp[i][j - 1], & s[i - 1] \neq t[j - 1] & \quad (只能编辑字符串t) \end{aligned} \right.\)

class Solution {
    public boolean isSubsequence(String s, String t) {
        int maxLen = 0;
        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++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 只能编辑字符串t
                    dp[i][j] = dp[i][j - 1];
                }
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
        return maxLen == s.length();
    }
}