Python recursive solution


  • 1
    Z

    There are 2 different situation to consider.

    1. If there is no duplicate characters in the ring, we only need to find the closest character that equal to key[0], since there is no duplicates, we can choose either direction to look for the character, if the step to reach this character is x by one direction, to reach here through the other direction is len(ring) - x.

    2. If there are duplicates, we need to try the first match from both direction and choose the minimum steps.

    from collections import Counter
    
    class Solution(object):
        def findRotateSteps(self, ring, key):
            if not ring or not key: return 0
            self.duplicates = {i for i, v in Counter(ring).items() if v > 1}
            self.cache = {}
            return self.helper(ring, key)
            
        def helper(self, ring, key):
            if not key: return 0
            if (ring, key) in self.cache:
                return self.cache[(ring, key)]
            c = key[0]
            if c in self.duplicates:
                cw, ccw = ring.rfind(c), ring.find(c)
                res = 1 + min(len(ring) - cw + self.helper(ring[cw:] + ring[:cw], key[1:]), ccw + self.helper(ring[ccw:] + ring[:ccw], key[1:]))
            else:
                pos = ring.find(c)
                res = 1 + min(pos, len(ring) - pos) + self.helper(ring[pos:] + ring[:pos], key[1:])
            self.cache[(ring, key)] = res
            return res
    

  • 0
    L

    @zhongyuan9817 Great solution, but you got your clockwise and counter clockwise mixed up


Log in to reply
 

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