from collections import defaultdict
from bisect import bisect_left
class Solution(object):
def createMap(self, s):
# create a map. key is char. value is index of apperance in acending order.
posMap = defaultdict(list)
for i, char in enumerate(s):
posMap[char].append(i)
return posMap
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
posMap = self.createMap(t)
# lowBound is the minimum index the current char has to be at.
lowBound = 0
for char in s:
if char not in posMap: return False
charIndexList = posMap[char]
# try to find an index that is larger than or equal to lowBound
i = bisect_left(charIndexList, lowBound)
if i == len(charIndexList): return False
lowBound = charIndexList[i] + 1
return True
Easy to understand binary search solution


Great solution. The straightforward solution in other threads would have time complexity O(k*len(t)) and space O(1) for the followup question. This one (with preprocessed t) has time complexity O(log(len(t)) * sum(len(Sk)) + len(t)) and space complexity O(len(t)). This solution trades memory for speed. Correct me if I am wrong.

@WKVictor I think the time complexity for method hashing is more like
Max( len(t), log(len(t)) * k * len(s) )
, instead ofO(log(len(t)) * sum(len(sk)) + len(t))
. Cause if we scan sequence t from beginning to end, and add the indices to character hash, we already guaranteed the indices to appear in ascending order. So if we use a container likevector
to store the indices, hash construction should only take ~len(t) * amortized O(1)
, akaO(len(t))
time. And the binary search part still takesO(log(len(t)) * len(sk))
.

@WKVictor seems this could be a bit simpler
space complexity is length of t, we need to add an index value to our dictionary foreach element of t. You also have the overhead of the keys for t but this does not changed that fact that this is still O(length of t)
time complexity is 1 binary search through 1 dictionary entry for each character of s. Worst case the dictionary entry has all indexes of t so it's cost would be log of the length of t. Multiply that against length of s and you get O(length of s * log(length of t))

@ruixia said in Easy to understand binary search solution:
if i == len(charIndexList): return False
Can you please explain why we need to check this ?