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]
