# Python recursive solution

• 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
``````

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

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