Sharing my O(RK) DP python solution. Detailed explanation of improving from O(R^2K) to O(RK)


  • 0
    D

    First of all, I assume you understand the O(RK^2) dp solution. Which, at each step of the dp, requires going through the ring O(R) times. i.e.
    dp[i][j]=min( [ dp[i][k] + minStepFrom_i_to_k for k in range(len(ring)) if ring[k]==key[i-1] ] ) if ring[j]==key[i]
    (here I'm using python list comprehension notation)

    which means we are going through all the characters to determine the minimum steps. However, we just need to check the closest ones on the left and right! To see this, lets assume we are onto the ith character of the key and we wish to calculate the minimum steps required to get to all the characters on the ring same as key[i], and we are doing it on the jth character on the ring (such that ring[j]==key[i]). Then if we need to check the characters of previous key other than the closest ones, there exists a character at position u such that dp[i-1][u] leads to dp[i][j]. Suppose u is left to the left closest key[i-1], then from u to leftClosest takes at most leftClosest-u steps. However, dp[i-1][u]+(j-u)<dp[i-1][leftClosest]+(j-leftClosest), which means dp[i-1][leftClosest] - dp[i-1][u] > leftClosest - u. This is impossible since we can just take at most leftClosest - u steps to get from u to leftClosest, it should be the case that dp[i-1][leftClosest] - dp[i-1][u] <= leftClosest - u, therefore dp[i-1][leftClosest] is not optimal! (same argument applies to characters right to the rightClosest)

    Therefore we just need to find the position of occurences of key[i-1] just left and right to the occurrences of key[i] in the ring! This is exactly what the subroutine findRange does. It takes in the indices of key[i-1] in the ring and the indices of key[i] in the ring, and it returns the indices of the left closest and right closest indices. Also to speed up the process, I used a dictionary to store the mapping from character to indices of that character on the ring to speed up the look-ups. The subroutine runs in O(R) time and each time after the left and right indices has been found the looping also takes O(R) time. The result is an O(R) inner loop and an O(RK) algorithm.

    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        # build dictionary of ring from character to list of indices in the ring
        # then the ring can be thrown away since d has all the information. Hooray!
        d={}
        l=len(ring)
        for i in range(l):
            c=ring[i]
            if c not in d:
                d[c]=[]                                                                                               
            d[c].append(i)
        
        # build the dp array
        # here -1 means cannot be reached
        dp=[[-1 for _ in range(l)] for _ in range(len(key))]
        
        # populate the intitial state        
        for i in d[key[0]]:
            dp[0][i]=min(i, l-i)
        
        # build the dp array
        for j in range(1,len(key)):
            # if two consecutive letters in the key are the same
            # then we can carry over previous calculations
            if key[j]==key[j-1]:
                dp[j]=dp[j-1]
            # else we have to look left and right to get the minimum steps needed
            else:
                curIndices=d[key[j]]
                left, right = self.findRange(d[key[j-1]],curIndices, l)
                for k in range(len(curIndices)):
                    dp[j][curIndices[k]]=min( dp[j-1][(left[k]+l)%l]+curIndices[k]-left[k], dp[j-1][right[k]%l]+right[k]-curIndices[k])
            
        minStep=min([step for step in dp[-1] if step!=-1])
                       
        return minStep+len(key)
        
        # a subroutine that finds the closest indices of the previous character to the left and right
        # this can be done in linear time
    def findRange(self, prevRange, nextRange, l):
        extendedRange=[prevRange[-1]-l]+prevRange+[prevRange[0]+l]
        left=[]
        right=[]
        j=0
        for i in range(len(nextRange)):
            
            while extendedRange[j+1]<nextRange[i]:
                j+=1
            left.append(extendedRange[j])
        
        j=len(extendedRange)-1
        for i in range(len(nextRange)-1,-1,-1):
            while extendedRange[j-1]>nextRange[i]:
                j-=1
            right.insert(0,extendedRange[j])
        return left, right

Log in to reply
 

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