leetcode_0392

Posted on | In , ,

题目

392. 判断子序列

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

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

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

示例 1:

1
s = "abc", t = "ahbgdc"

返回 true.

示例 2:

1
s = "axc", t = "ahbgdc"

返回 false.

后续挑战 :

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

答案

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n = len(s)
        m = len(t)
        i = 0
        j = 0
        while i<n and j < m:
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        if i == n:
            return True
        else:
            return False

动态规划

官方题解里给出了一个动态规划的解法。

思路：

每个位置之后遇到26个小写字母的情况是如何的？

位置是0 ~ m-1​ ; 最后再加上一个全 m 的向量（26个小写字母）表示在 m 这个越界位置，遇到某个字母是不可能的。

那么对于 m-1 位置上的表示 m-1开始往后某个字母的位置，因为m-1 开始只有一个字母，其他的都不可能出现了，所以这一列只有有的那个字母表示为 m-1，其他的都是m；以此往前完成 $f[i][j]$ 最终得到一个转换表。

后来不论来什么字符串在第一个位置查，从第一个位置开始出现那这个字符串第一个字符的位置。所以这个方法虽然复杂了一点，但是完全适用于问题中的后续挑战。

题解：

思路及算法

考虑前面的双指针的做法，我们注意到我们有大量的时间用于在 tt 中找到下一个匹配字符。

这样我们可以预处理出对于 tt 的每一个位置，从该位置开始往后每一个字符第一次出现的位置。

我们可以使用动态规划的方法实现预处理，令 $f[i][j]$ 表示字符串 tt 中从位置 $i$ 开始往后字符 $j$ 第一次出现的位置。在进行状态转移时，如果 $t$ 中位置 $i$ 的字符就是 $j$，那么 $f[i][j]=if[i][j]=i$，否则 $j$ 出现在位置 i+1i+1 开始往后，即 $f[i][j]=f[i+1][j]$，因此我们要倒过来进行动态规划，从后往前枚举 $i$。

这样我们可以写出状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        f = [[0] * 26 for _ in range(m)]
        f.append([m] * 26)

        for i in range(m - 1, -1, -1):
            for j in range(26):
                f[i][j] = i if ord(t[i]) == j + ord('a') else f[i + 1][j]
        
        add = 0
        for i in range(n):
            if f[add][ord(s[i]) - ord('a')] == m:
                return False
            add = f[add][ord(s[i]) - ord('a')] + 1
        
        return True