题目描述

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 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。旋转 ring 拼出 key 字符 key[i] 的阶段中：

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

算法1

(动态规划) $O(n*m^2)$

题解：动态规划。这题比较复杂的地方一个是状态表示和顺时针和逆时针两个方向。

状态表示：dp[i][j]代表已经拼好key[0:i]并且ring[j]恰好指向12点钟方向的最小答案。这里需要注意的是，必须要求key[i] = ring[j]，因为求最小步数，我们没有必要在完成匹配按下按钮后又转动轮盘。

状态初始化：对于所有的ring[i] = key[0]，dp[0][i] = min(i + 1,m - i + 1)。分别表示匹配第一个字符最终ring[i]指向12点钟方向所需要的步数，min函数中分别代表顺时针和逆时针需要的步数，加上1时因为还需要按下当前字符。

状态转移：我们知道只有当key[i] = ring[j]的时候才是合法值，那么对于key[i] != ring[j]直接赋值为INT_MAX。我们考虑dp[i][j]可以由哪些状态转移而来呢？因为上一个状态也必须是合法状态，所以必须有key[i - 1] = ring[k]才可以从dp[i - 1][k]转移到dp[i][j]。因此对于所有的ring[k] = key[i - 1]，有cost = dp[i - 1][k] + min((j - k + m) % m,(k - j + m) % m) + 1，min中分别代表的也是顺时针和逆时针两种情况。

结果计算：最后停止的位置肯定是key中最后一个字符，所以我们需要遍历所有的ring[i] = key[n - 1]，都是一个合法的位置，比较其最小值。

时间复杂度分析:总共三层循环$O(n*m^2)$

C++ 代码

    int findRotateSteps(string ring, string key) {
        int m = ring.length(),n = key.length(),cost = 0,res = INT_MAX;
        int dp[n][m];
        memset(dp,0,n * m * sizeof(int));
        for(int i = 0 ; i < m ; i ++)
            if(ring[i] == key[0])
                dp[0][i] = min(i + 1,m - i + 1);
        for(int i = 1 ; i < n ; i ++)
        {
            for(int j = 0 ; j < m ; j ++)
            {
                dp[i][j] = INT_MAX;
                if(key[i] == ring[j])
                {
                    for(int k = 0 ; k < m ; k ++)
                    {
                        if(key[i - 1] == ring[k])
                        {
                            cost = dp[i - 1][k] + min((j - k + m) % m,(k - j + m) % m) + 1;
                            dp[i][j] = min(dp[i][j],cost);
                        }
                    }
                }
            }
        }
        for(int i = 0; i < m ; i ++)
            if(ring[i] == key[n - 1])
                res = min(res,dp[n - 1][i]);
        return res;
    }