Leetcode 392. Is Subsequence

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，依次比较字符串s和t中的字符。Version 2，为Leetcode 792做铺垫，先将t中的字符以及对应的索引保存到字典中，相同字符对应的索引构成一个有序序列，然后依次s中的每个字符，在t中查找其对应的字符索引位置，如果字符在t中不存在，直接返回False，pre表示单词中前一个字符在t中的索引位置，每次查找使用二分查找，如果返回的序列索引位置等于序列的长度，即pre位置之后的t中没找到对应的当前字符，则返回False，否则，更新pre为当前字符在t中的索引位置。

• Version 1

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

• Version 2

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        stat = collections.defaultdict(list)
        for i, ch in enumerate(t):
            stat[ch].append(i)
        pre = -1
        for ch in s:
            if ch not in stat:
                return False
            index = bisect.bisect(stat[ch], pre)
            if index == len(stat[ch]):
                return False
            else:
                pre = stat[ch][index]
        return True

Reference

1. https://leetcode.com/problems/is-subsequence/