WEEK#10 Dynamic Programming_Freedom Trail

Description of the Problem

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:

image.png

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 duplicate characters in both strings.
It's guaranteed that string key could always be spelled by rotating the string ring.


Thinking Process

All letters in ring have a smallest cost to travel to another letter in ring.
So for a ring of size n, we construct a 2-d array M[n][n], in which M[i][j] means the smallest cost travel from ring[i] to ring[j].
In this way, what we need will be :

Pointer and Result are initialized as 0.
For i ∈ (0, key.length)
1. Find j, so that ring[j] = key[i];
2. Result += M[Pointer][j];
3. Pointer = j;

This method can only work out very limited test cases, for it is rather static than dynamic. It is unable to take all the moves into account, thus can't work out the best solution.
Every step that the algorithm takes could all have an influence on the result, yet this method can only choose the smallest cost at current step, overlooking that taking the smallest step now may result in a bigger cost later on.
For example, ring = "iotfo", key = "fioot"
When currently pointing to 'i', and wish to go to 'o', the cost of left-side 'o' and right-side 'o' are the same, but only by taking the right-side one can we get the best solution, cause its closer to 't' than the left-side one.

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int length = ring.size();
        vector<vector<int>> Matrix = construct(length);
        int result = 0, pointer = 0;
        for (int i = 0; i < key.length(); i++) {
            int findleft = 0, findright = 0;
            bool jflag = false;
            for (int j = pointer; j < length; j++) {
                if (ring[j] == key[i]) {
                    findright = j;
                    break;
                }
                if (j == length-1 && jflag == false) {
                    j = -1;
                    jflag = true;
                }
            }
            bool kflag = false;
            for (int k = pointer; k >= 0; k--) {
                if (ring[k] == key[i]) {
                    findleft = k;
                    break;
                }
                if (k == 0 && kflag == false) {
                    k = length;
                    kflag = true;
                }
            }
            int smaller = Matrix[pointer][findleft] <= Matrix[pointer][findright] ? Matrix[pointer][findleft] : Matrix[pointer][findright];
            result += smaller;
            if (Matrix[pointer][findleft] <= Matrix[pointer][findright])
                pointer = findleft;
            else
                pointer = findright;
        }
        return result;
    }

    vector<vector<int>> construct(int length) {
        vector<vector<int>> Matrix;
        Matrix.resize(length);
        for (int i = 0; i < length; i++)
            Matrix[i].resize(length);

        for (int i = 0; i < length; i++)
            Matrix[i][i] = 1;

        for (int i = 0; i < length; i++) {
            int count = 1;
            bool flag = false;
            for (int j = i + 1; j < length; j++) {
                if (flag == false)
                    Matrix[i][j] = ++count;
                if (count >= length / 2 + 1 && flag == false) {
                    flag = true;
                    continue;
                }
                if (flag) {
                    if (length % 2 == 1)
                        Matrix[i][j] = count--;
                    else
                        Matrix[i][j] = --count;
                }
            }
        }

        for (int i = 1; i < length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                Matrix[i][j] = Matrix[j][i];
            }
        }
        return Matrix;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 今天姐姐说她的小狗雪花记性越来越不好了,经常在外面转几圈才想起回家,视力不济,听力也不好,还胡乱小便。。。好像患上...
    悠然的桥阅读 489评论 0 7
  • 《作为意志和表象的世界》开篇第一句就是:“世界是我的表象”。在叔本华看来,整个世界首先是作为人类的印象而存在,对人...
    摄影师柳丁阅读 188评论 0 0
  • 今天和朋友聊天,她说觉得我是幸运的,我也值得这份幸运。可是直到聊天结束,我都不解她口中的幸运,于我是什么。1 自小...
    晨creezy阅读 274评论 0 0