1 题目描述

电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

提示
ring 和 key 的字符串长度取值范围均为 1 至 100；
两个字符串中都只有小写字符，并且均可能存在重复字符；
字符串 key 一定可以由字符串 ring 旋转拼出。

2 题解

2.1 贪心

首先拿到这个题后，感觉利用贪心算法可以解决，于是乎写出了如下的代码：

    def my_method(self, ring, key):

        ring_len = len(ring)
        key_len = len(key)
        distance = ring_len  # init distance， 记录一轮 转 的最优 距离
        nearest_index = 0  # 保留一轮 转 中 的 ring中的index
        res = 0

        for k in range(key_len):
            for index in range(ring_len):
                """ 找到一个匹配的"""
                if ring[index] == key[k]:
                    """ 选择正向转还是逆向转 """
                    new_distance = min(index, ring_len - index)

                    """ 更新distance, nearest_index """
                    if new_distance < distance:
                        distance = new_distance
                        nearest_index = index

                    # if new_distance == distance:
                    #     return min(self.my_method(ring[nearest_index:] + ring[:nearest_index], key[k:]),
                    #                self.my_method(ring[distance:] + ring[:distance], key[k:]))

            """ 按中心按钮 """
            res += distance + 1
            """ 更新 ring, distance, nearest_index """
            ring = ring[nearest_index:] + ring[:nearest_index]
            distance, nearest_index = ring_len, 0

        return res

然后发现wa。后来仔细想了一下，是这么回事：

"""
那么问题来了，这是一种基于贪心的算法，每一次保证一轮中是最优的，但是在这一轮进行完后改变了 ring， 影响了后面的每一轮，
这就要求全局最优。而贪心只保证了局部最优

例如测试用例：ring="nyngl" key="yyynnnnnnlllggg"就没过。
也就是说当 距离相等的时候该做如何选择， 如 yngln ， 我们下一个 需要匹配的是 n ， 是逆转为nglny 还是正转为nyngl
"""

后续又添加了条件，当相等的时候，也就是上面注释的代码，但是递归太深，导致栈溢出。

2.2 递归

下面代码参考leetcode评论区大佬发狂的橘子，用到了python的缓存机制。

这个方法非常巧妙地简化了当ring中存在多个与key某一位匹配时的选择问题。

str.find(s)是找s在str中最靠左边的下标

str.rfind(s)是找s在str中最靠右边的下标。

不论这一刻有多少个匹配的，但你转的方式只有两种。将此轮所有匹配的（包括一个）简化为两种旋转方式。

    def findRotateSteps(self, ring: str, key: str) -> int:

        key_len = len(key)

        import functools
        @functools.lru_cache(None)
        def helper(index, s):
            if index == key_len:
                return 0
            left_index = s.find(key[index])
            right_index = s.rfind(key[index])
            res = min(left_index + helper(index + 1, s[left_index:] + s[:left_index]),
                      len(s) - right_index + helper(index + 1, s[right_index:] + s[:right_index])) + 1
            return res

        return helper(0, ring)

2.3 动态规划

用一个n*m的的数组，dp[i][j]表示第key中前i个字符对齐后，ring中第j个字符转到12点位需要的最少次数(逆时针或者顺时针转)，

现在问题是当前 i-1个字符对齐时，如何求第i个字符对齐

在下图中，整条线代表的ring这个序列，在上一轮中，我们在ring中找到了与key中第i-1个匹配的字符index=k（最优），并将它移动了12点位。

此轮中，我们在ring中找到了一个与key中第i个字符匹配的字符index=j，那么我们只需要计算将index=j转到index=k的的最少次数（index=j在上一轮操作中已经转到了12点位，现在index=j就是12点位), 然后再加上上一次已经计算出来的不就是这次的嘛。

dp[i][j] = dp[i - 1][k] + dist,dist为 index=j转到index=k的的最少次数。

转的方式无非两种，逆时针和顺时针。

图中红色线段为index=j逆时针转到index=k的距离，为 abs(j-k)
图中两段蓝色线段和为index=j顺时针转到index=k的距离，则距离为 ring_len-abs(j-k)

通过上面的分析我们可以得到这样的一个方程

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

但是在ring中可能存在不止一个满足与key中第i个字符匹配的字符，那就说明我们需要遍历ring（包裹一层循环)，遇到更优的dp[i][j]还要进行更新。所以，最终的状态转移方程为

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

代码：


    def dp_method(self, ring, key):

        ring_len = len(ring)
        key_len = len(key)
        dp = [[10001] * ring_len for _ in range(key_len)]

        # init dp
        for i in range(ring_len):
            if ring[i] == key[0]:
                dp[0][i] = min(i, ring_len - i)

        for key_index in range(1, key_len):
            for ring_index in range(ring_len):
                """ 此轮找到了一个匹配的 """
                if ring[ring_index] == key[key_index]:
                    """ 包一层循环，在ring中 更新 dp """
                    for inner_ring_index in range(ring_len):
                        """ 在ring中 上一个匹配的 """
                        if key[key_index - 1] == ring[inner_ring_index]:
                            dist = abs(ring_index - inner_ring_index)
                            dp[key_index][ring_index] = min(dp[key_index][ring_index],
                                                            min(dist, ring_len - dist) + dp[key_index - 1][
                                                                inner_ring_index])
        """ 
        最终我们要返回的肯定是key的所有字符都被依次对齐了， 那么结果肯定在dp[key_len-1]中，
        min一下其实就是筛选出 在ring中匹配 key最后一个字符 的那个字符到12点位的最短距离
        加上 key_len 的原因是前面我们没有在对齐后按中心按钮，一共需要按key_len 次 """
        return min(dp[key_len - 1]) + key_len