python solutions


  • 0
    Z
    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)
    

Log in to reply
 

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