leetcode 514. Freedom Trail 自由之路 + 旋转堆密码 + 动态规划DP解决

Love The Way You Lie 2022-06-03 02:11 159阅读 0赞

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\]:  
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\].  
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:

![这里写图片描述][SouthEast]

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:  
Length of both ring and key will be in range 1 to 100.  
There are only lowercase letters in both strings and might be some duplcate characters in both strings.  
It’s guaranteed that string key could always be spelled by rotating the string ring.

题意很简单，就是可以顺时针和逆时针旋转时针，统计旋转玩key需要的最少的step，注意旋转到相应元素需要按button，这个需要key的size次，所以最后加上这个次数。

很明显需要DP解决，其实想了好久不知道该怎么做，所以还是看了很多的做法。

做法1：通过匹配的方法，从key中一一取出一个字符，在ring中匹配，得到转到该字符的最小转数。注意，除了第一个字符外，剩下的字符的转数需要由上一个字符的转数加上转动次数决定。本题需要考虑的是当出现了顺、逆时针转动时都有相同转数的匹配，这是应该选择顺时针还是逆时针，这里需要将两种结果与下一个匹配的结果相加进行比较来选择。dp\[i\]\[j\]表示key的从0到i的字符匹配到ring的j字符需要的最小的step，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findRotateSteps(string ring, string key) 
        {
            int row = key.length(), col = ring.length();
            vector<vector<int>> dp(row, vector<int>(col, INT_MAX));
            int minCount = INT_MAX;
    
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (key[i] == ring[j])
                    {
                        if (i == 0)
                            dp[i][j] = min(abs(i-j),col-abs(i-j));
                        else
                        {
                            for (int k = 0; k < col; k++)
                            {
                                if (dp[i - 1][k] != INT_MAX)
                                {
                                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(k - j), col - abs(k - j)));
                                }
                            }
                        }
                        if (i == row - 1)
                            minCount = min(minCount, dp[i][j]);
                    }
                }
            }
            return minCount + key.length();
        }
    };

这个DP的做法是从0开始遍历直至key结束，我还看到一种更加简单的做法，

做法2：dp\[i\]\[j\]表示转动从i位置开始的key串所需要的最少步数(这里不包括spell的步数，因为spell可以在最后统一加上)，此时表盘的12点位置是ring中的第j个字符。不得不佩服这样的设计的确很巧妙，我们可以从key的末尾往前推，这样dp\[0\]\[0\]就是我们所需要的结果，因为此时是从key的开头开始转动，而且表盘此时的12点位置也是ring的第一个字符。现在我们来看如何找出递推公式，对于dp\[i\]\[j\]，我们知道此时要将key\[i\]转动到12点的位置，而此时表盘的12点位置是ring\[j\]，我们有两种旋转的方式，顺时针和逆时针，我们的目标肯定是要求最小的转动步数，而顺时针和逆时针的转动次数之和刚好为ring的长度n，这样我们求出来一个方向的次数，就可以迅速得到反方向的转动次数。为了将此时表盘上12点位置上的ring\[j\]转动到key\[i\]，我们要将表盘转动一整圈，当转到key\[i\]的位置时，我们计算出转动步数diff，然后计算出反向转动步数，并取二者较小值为整个转动步数step，此时我们更新dp\[i\]\[j\]，更新对比值为step + dp\[i+1\]\[k\]，这个也不难理解，因为key的前一个字符key\[i+1\]的转动情况suppose已经计算好了，那么dp\[i+1\]\[k\]就是当时表盘12点位置上ring\[k\]的情况的最短步数，step就是从ring\[k\]转到ring\[j\]的步数，也就是key\[i\]转到ring\[j\]的步数，用语言来描述就是，从key的i位置开始转动并且此时表盘12点位置为ring\[j\]的最小步数(dp\[i\]\[j\])就等价于将ring\[k\]转动到12点位置的步数(step)加上从key的i+1位置开始转动并且ring\[k\]已经在表盘12点位置上的最小步数(dp\[i+1\]\[k\])之和。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findRotateSteps(string ring, string key) 
        {
            int row = key.length(), col = ring.length();
            vector<vector<int>> dp(row+1, vector<int>(col));
    
            for (int i = row - 1; i >= 0; i--)
            {
                for (int j = 0; j < col; j++)
                {
                    dp[i][j] = INT_MAX;
                    for (int k = 0; k < col; k++)
                    {
                        if (key[i] == ring[k])
                        {
                            int step = min(abs(j - k), col - abs(j - k));
                            dp[i][j] = min(dp[i][j], dp[i + 1][k] + step);
                        }
                    }
                }
            }
    
            return dp[0][0] + row;
        }
    };

[SouthEast]: /images/20220603/43698fbc9da24d87863b2d553a713513.png