# python solutions

• ``````class Solution(object):
def findRotateSteps(self, ring, key):
"""
:type ring: str
:type key: str
:rtype: int
"""
dp = [[min(i, len(ring)-i) for i in xrange(len(ring))]]
dp.extend([[float('inf')] * len(ring) for _ in xrange(len(key))])
for i in xrange(1, len(key)+1):
for j in xrange(len(ring)):
if ring[j] != key[i-1]:
continue
min_step = float('inf')
for k in xrange(len(ring)):
if dp[i-1][k] == float('inf'):
continue
step = abs(k - j)
step = min(step, len(ring) - step) + 1 + dp[i-1][k]
min_step = min(min_step, step)
dp[i][j] = min_step
return min(dp[-1])

def bt_findRotateSteps(self, ring, key):
"""
:type ring: str
:type key: str
:rtype: int
"""
def backtracking(ring_pos, key_pos):
if visited.get(ring_pos, {}).get(key_pos):
return visited[ring_pos][key_pos]
if key_pos >= len(key):
return 0
min_step = float('inf')
for i in xrange(len(ring)):
if ring[i] == key[key_pos]:
step = abs(i - ring_pos)
step = min(step, len(ring) - step) + 1
step += backtracking(i, key_pos + 1)
min_step = min(min_step, step)
return visited.setdefault(ring_pos, {}).setdefault(key_pos, min_step)

visited = {}
return backtracking(0, 0)
``````

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