leetcode-判断子序列

392. 判断子序列

题解：

1. 初始化两个指针，分别指向字符串s和t的起始位置。
2. 遍历字符串t，如果当前字符与s中的指针所指字符相同，则将s中的指针向后移动一位。
3. 如果遍历完t后，s中的指针指向了s的末尾，说明s是t的子序列，返回True；否则返回False。

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

对于进阶问题，如果有大量的s字符串需要检查它们是否为t的子序列，每次遍历t会耗费很多时间。为了提高效率，可以预处理t，创建一个索引，以便快速跳过不匹配的字符。

1. 预处理t:
   • 创建一个字典来存储字符在t中出现的所有位置（indexes），为此你可以使用字典里的列表。
   • 对每个字符，存储它每次出现在t中的索引。
2. 对于每个s进行检查:
   • 使用二分查找来找出s中每个字符在t中的正确位置，确保这个位置在上一个字符位置之后。

这个方法利用了“t的长度可能远大于s”和“可以接受预处理开销以换取整体效率提高”的特点。以下是对应的代码思路。

from collections import defaultdict
import bisect

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        char_dict = defaultdict(list)
        for index, char in enumerate(t):
            char_dict[char].append(index)
        
        prev_pos = -1
        for char in s:
            if char not in char_dict:
                return False
            idx_list = char_dict[char]
            curr_pos = bisect.bisect_right(idx_list, prev_pos)
            if curr_pos == len(idx_list):
                return False
            prev_pos = idx_list[curr_pos]
        return True

bisect是Python中的一个标准库模块，主要用于处理有序列表的插入和查找操作。

bisect模块提供了几种主要的函数来对有序列表进行操作：

1. bisect.bisect(list, x): 返回插入点索引，该索引是列表中第一个大于等于x的元素的索引。如果所有元素都小于x，则返回列表的长度。
2. bisect.bisect_left(list, x): 返回插入点索引，该索引是列表中第一个大于x的元素的索引。如果所有元素都小于或等于x，则返回列表的长度。
3. bisect.bisect_right(list, x): 与bisect.bisect类似，返回的是第一个大于x的元素的索引，但如果有多个相同的元素，它会返回这些相同元素中最后一个的索引。
4. bisect.insort(list, x): 将指定的值x插入到有序列表中，并保持列表的排序。这是在列表中插入元素时保持其有序性的有效方法。
5. bisect.insort_left(list, x): 类似于insort，但它是将元素插入到列表中，使得插入后列表仍然有序，且新插入的元素位于现有相等元素的前面。
6. bisect.insort_right(list, x): 类似于insort，但它是将元素插入到列表中，使得插入后列表仍然有序，且新插入的元素位于现有相等元素的后面。