题目描述：

LeetCode 514. Freedom Trail

In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:

1. You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring's characters at the 12:00 direction, where this character must equal to the character key[i].
2. If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.

Example:

Input: ring = "godding", key = "gd"
Output: 4
Explanation:
 For the first key character 'g', since it is already in place, we just need 1 step to spell this character. 
 For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
 Also, we need 1 more step for spelling.
 So the final output is 4.

Note:

1. Length of both ring and key will be in range 1 to 100.
2. There are only lowercase letters in both strings and might be some duplcate characters in both strings.
3. It's guaranteed that string key could always be spelled by rotating the string ring.

题目大意：

给定一个拨盘，拨盘上的字符为ring（顺时针方向排列），以及一个关键词key。

拨盘的顶点初始对准ring的第一个字符，拨盘可以顺时针拨动，也可以逆时针拨动。

每拨动一个字符记1步，按一下按钮也记1步。

求利用拨盘得到关键词所需的最小步数。

注意：

1. ring和key的长度不超过100。
2. 字符串中只包含小写字母。
3. 输入确保可以利用ring得到key。

解题思路：

动态规划（Dynamic Programming）

利用字典dp记录当拨盘位于某位置时，所需的最少步数。

状态转移方程：

dp[k][i] = min(dp[k][i], dp[k - 1][j] + min(abs(i - j), len(ring) - abs(i - j)))

其中k表示当前字符在key中的下标，i表示当前字符在ring中的下标，j表示上一个字符在ring中的下标。

上式可以利用滚动数组化简为一维，节省空间开销。

Python代码：

class Solution(object):
    def findRotateSteps(self, ring, key):
        """
        :type ring: str
        :type key: str
        :rtype: int
        """
        rlist = collections.defaultdict(list)
        for i, r in enumerate(ring):
            rlist[r].append(i)
        rsize = len(ring)
        dp0 = {0 : 0}
        for c in key:
            dp = {}
            for i in rlist[c]:
                dp[i] = 0x7FFFFFFF
                for j in dp0:
                    dp[i] = min(dp[i], dp0[j] + min(abs(i - j), rsize - abs(i - j)))
            dp0 = dp
        return min(dp.values()) + len(key)

 

本文链接：http://bookshadow.com/weblog/2017/03/05/leetcode-freedom-trail/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码