【Leetcode】392. Is Subsequence

class Solution1(object): """ 双指针 """ def isSubsequence(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) > len(t): return False if len(s) == 0: return True s_index = 0 for t_index in range(len(t)): if t[t_index] == s[s_index]: s_index += 1 if s_index == len(s): return True return False class Solution2: """ pythonic 的方法， 使用 python 的迭代器 对于s中的每个元素，我们判断是否在迭代器中， 如果在，那么迭代器的指针就会指向迭代器找到的第一个元素的位置， 下次的操作会从该位置开始 faster than 90.44% """ def isSubsequence(self, s, t): itera =iter(t) return all(c in itera for c in s) class Solution3(object): """ 这道题的flow up, 给你一个母串t, 给你大量s让你去判断每个s是否匹配， 如果按照先前的做法，那么每次得遍历母串造成大量得时间开销 我们可以先将母串每个字母出现的index保存起来，每次从中找出一个满足条件的index, 而这个条件就是找出的index必须比上一个字母的index大 我们用binary search 来找第一个大于x的值 """ def isSubsequence(self, s, t): from collections import defaultdict dictionary = defaultdict(list) for index, ele in enumerate(t): dictionary[ele].append(index) last_index = -1 for char in s: if char not in dictionary: return False else: find = self.binarySearch(dictionary[char], last_index) if find == -1: return False else: last_index = find return True def binarySearch(self, array, value): if value >= array[-1]: return -1 low, high = 0, len(array) while(low < high): middle = (low + high) //2 if array[middle] <= value: low = middle + 1 else: high = middle return array[low]