392. 判断子序列

392. 判断子序列

难度
简单

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = “abc”, t = “ahbgdc”
返回 true.
示例 2:
s = “axc”, t = “ahbgdc”
返回 false.
后续挑战 :
如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢:
特别感谢 @pbrother 添加此问题并且创建所有测试用例。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s)>len(t):
            return False
        a=list(s)
        for i in t:
            if not a:
                return True
            if i==a[0]:
                a.pop(0)
        return not a

1. 看到这道题第一反应把s变换成列表，然后遇到相等的就出来，最后判断s为不为空就ok。

class Solution:
    import copy
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s)>len(t):
            return False
        Tcopy=copy.deepcopy(t)
        for i in s:
            if i in Tcopy:
                index=Tcopy.index(i)
                Tcopy=Tcopy[index+1:]
            else:
                return False
        return True

1. 遍历一下s然后利用index从左往右查找得特性在Tcopy里面找到index，更新一下Tcopy,如果s中的值不在Tcopy则直接返回False.

class Solution:
    import copy
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s)>len(t):
            return False
        p1=0
        p2=0
        while p2<len(t):
            if p1==len(s):
                return True
            if t[p2]==s[p1]:
                p1+=1
                p2+=1
            else:
                p2+=1
        return p1==len(s)

跟前面思路类似，使用双指针来实现。

最后

以上就是独特丝袜为你收集整理的392. 判断子序列的全部内容，希望文章能够帮你解决392. 判断子序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。