【leetcode】514. Freedom Trail

题目如下：

解题思路：记dp[i][j]为使ring中的第i个字符对应key的第j个字符需要操作的最少的次数，那么有 dp[i][j] = min (dp[k][j-1] + distance(i,k))， k表示ring中和key[j-1]相对应的字符，而distance(i,k) 表示ring中i与k的最短距离，因为ring中和key[j-1]相对应的字符可能有多个，所以需要求最小值。最后只要找出ring中与key最后一个字符相同的字符出现的所有位置，假设为m,取 min(dp[m][-1]）的最小值即可。

代码如下：

class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        dp = [[float('inf')] * len(key) for _ in ring]

        for i in range(len(ring)):
            if ring[i] == key[0]:
                dp[i][0] = min(i,len(ring) - i) + 1
        for j in range(1,len(key)):
            for i in range(len(ring)):
                if key[j] == ring[i]:
                    for k in range(len(ring)):
                        #if i == k:continue
                        if ring[k] == key[j-1]:
                            diff = abs(k - i)
                            dp[i][j] = min(dp[i][j],dp[k][j-1] + min(diff,len(ring) - diff) + 1)
        res = float('inf')
        for i in range(len(ring)):
            if ring[i] == key[-1]:
                for j in range(len(dp[i])):
                    res = min(res,dp[i][-1])

        return res