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
Great solution. The straightforward solution in other threads would have time complexity O(k*len(t)) and space O(1) for the follow-up 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 of
O(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 like
vector to store the indices, hash construction should only take ~
len(t) * amortized O(1), aka
O(len(t)) time. And the binary search part still takes
O(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))
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.