Easy to understand binary search solution


  • 26
    R
    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
    

  • 1
    W

    Brilliant! This solution is more efficient for the follow up question.


  • 0
    W

    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.


  • 0
    S

    @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)).


  • 2

    @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))


  • 0
    C

    @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 ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.