514. Freedom Trail

week10

难度：Hard

题目链接

题目描述

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:

example
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.

题目分析

  题目看起来很复杂，其实很简单，说的是辐射4中的一个小游戏，即通过旋转按钮将指针指向对应的字符串，从而根据key按顺序来按出所有的字母，这个按钮可以顺时针或者逆时针旋转，要求算出拼出key的最少步数（按下按钮也算一步）。

解题思路

  因为旋钮可以左旋或者右旋，所以每一次的旋转过后的指针都有可能不一样，因为旋钮上的字母是可重复的。可以说每一次的最短路径都不一样。因此我们不能简单的认为每一次都取最短路径就行了，因为上一次的选择会影响下一次的进行。

  这样看来这道题目明显就是动态规划中的最短路径问题，我们可以计算一下每个状态下的步数，到达下一个状态取上一个状态+到达下一个状态的步数的最小值，类似于最短路径的做法。因为知道一开始指针必定是指向12点钟方向，所以可以从后往前推，f(i,j) = min(f(i,j),abs(j-k) + f(i+1,k)),求得的f(0)即是最小的步数。定义一个二维数组或者二维向量即可保存其状态，其中i为当前已匹配数，j为指针的方向（指向的位置）。

  因为每一次都要按一下确认，所以直接在最后加上key的长度。因为key和ring长度不定，建议使用二维向量。

第一次尝试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution
{
  public:
    int findRotateSteps(string ring, string key)
    {
        vector<vector<int>> steps(key.length() + 1, vector<int>(ring.length()));
        for (int i = key.length() - 1; i >= 0; i--)
        {
            char next = key[i];
            for (int j = 0; j < ring.length(); j++)
            {
                steps[i][j] = INT_MAX;
                for (int k = 0; k < ring.length(); k++)
                {
                    if (next == ring[k])
                    {
                        int dist = abs(j - k);
                        int step = min(dist, (int)ring.length() - dist);
                        steps[i][j] = min(steps[i][j], step + steps[i + 1][k]);
                    }
                }
            }
        }
        return steps[0][0] + key.length();
    }
};

结果反思

第一次测试
第一次测试

  经过测试之后，这种方法的确可行，但看了运行结果发现这个算法运行的并不是很快，当ring变得很长时，花费了很多的时间。在逐步调试之后，一个主要的问题就是在很多不必要的状态下进行了计算。比如有些状态始终不会达到的，没有计算的必要，而且这个三重循环就注定了运行时间并不会很短。

  思考了一下并参考了别人的方法，觉得还是使用递归来逐步计算比较好，因为左旋和右旋只有2种，但key同一个字母的个数却不止2种，状态还是设定不够到位，应该把指针的位置作为i，匹配数作为j，这样计算时就少了一些分叉。

  比如要找i，如果参照第一种做法，就会遍历所有到i的路径，而第二种做法就只会左旋和右旋到不同i的位置，找出最短的，不必到遍历到多余的i。

改良后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution
{
  public:
    int findRotateSteps(string ring, string key)
    {
        steps = vector<vector<int>>(ring.length(), vector<int>(key.length(), INT_MAX));
        return rotate(ring, key, 0, 0) + key.length();
    }
    int rotate(string &ring, string &key, int pointer, int pos)
    {
        int right = 0, left = 0;
        if (pos >= key.size())
        {
            return 0;
        }
        if (steps[pointer][pos] != INT_MAX)
        {
            return steps[pointer][pos];
        }
        int lp = pointer;
        int rp = pointer;
        while (ring[lp] != key[pos])
        {
            lp--;
            left++;
            if (lp < 0) //判断是否越界。
            {
                lp = ring.size() - 1;
            }
        }
        while (ring[rp] != key[pos])
        {
            rp++;
            right++;
            if (rp == ring.size()) //判断是否越界。
            {
                rp = 0;
            }
        }
        left += rotate(ring, key, lp, pos + 1);
        right += rotate(ring, key, rp, pos + 1);
        return steps[pointer][pos] = min(left, right);
    }

  private:
    vector<vector<int>> steps;
};

代码分析

  使用了递归避免了三重循环，从0，0开始一直匹配，而且每一个分叉只有左旋和右旋的分叉，减少了分叉的数量从而少计算了很多状态。其中有些状态可以被重复利用，就像很多条路若有一个交叉点，那么后面的最短路径的节点也是交叉的，不必再往后算。这又很像之前的frog jump这道题。修改后的算法居然超越了100%！还是第一次。。。

优化后的结果
优化后的结果

总结

  动态规划有时候感觉并不会这么容易想得到，虽然都知道通常解法是构建状态，确认策略，然后进行顺推或者倒退来得到结果。但不同的问题都有着不同的性质和解法，所以说解决这类问题只能依靠多熟悉这类问题，多优化多修改，第一次往往都得不到最佳的解法的。