Follow-up: Trade space for time and with binary search


  • 0
    A
    1. For follow-up. Trade space for time. Store char positions for t.
      s = aabac,
      t = aaabaac.
      {a: [0,1,2,4,5],
      b: [3],
      c: [6]}
    2. Initialize lowerBound = 0. Iterate over s, binary search the first position of the current char satisfying position >= lowerBound, update lowerBound with the found position + 1.
    3. Of course, you may use bisect instead of implementing findFirstPos https://docs.python.org/2/library/bisect.html

    Please let me know if there is any mistake. Thanks.

    class Solution(object):
        def isSubsequence(self, s, t):
            charPos = dict()
            for pos, char in enumerate(t):
                charPos.setdefault(char, []).append(pos)
            
            lowerBound = 0
            for char in s:
                if char not in charPos:
                    return False
                else:
                    firstPos = self.findFirstPos(charPos[char], lowerBound)
                    if firstPos == -1:
                        return False
                    else:
                        lowerBound = firstPos + 1
            return True
                    
                    
        def findFirstPos(self, poses, lowerBound):
            low = 0
            high = len(poses) - 1
            while low < high:
                mid = (high - low) / 2 + low
                if poses[mid] >= lowerBound:
                    high = mid
                else:
                    low = mid + 1
            if poses[low] >= lowerBound:
                return poses[low]
            else:
                return -1
    

Log in to reply
 

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