LeetCode 514. 自由之路（记忆化递归 / DP）

Michael阿明

发布于 2021-02-19 04:47:16

33500

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

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 旋转拼出。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/freedom-trail 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

直接暴力dfs搜索，超时

class Solution {	// 超时
    int steps = INT_MAX;
    int n;
    vector<vector<int>> pos;
public:
    int findRotateSteps(string ring, string key) {
        n = ring.size();
        pos.resize(26);
        for(int i = 0; i < ring.size(); i++)
            pos[ring[i]-'a'].push_back(i); //记录相同字符的所有位置
        dfs(key, 0, 0, 0);
        return steps;
    }
    void dfs(string& key, int start, int i, int step)
    {
        if(step >= steps)
            return;
        if(i == key.size())
        {
            if(step < steps)
                steps = step;
            return;
        }
        for(int j = 0; j < pos[key[i]-'a'].size(); j++)
        {
            int delta = min(abs(start-pos[key[i]-'a'][j]), n-abs(start-pos[key[i]-'a'][j]));
            dfs(key, pos[key[i]-'a'][j], i+1, step+delta+1);
        }
    }
};

class Solution {    //记忆化递归
    int n;
    vector<vector<int>> pos;
    vector<vector<int>> memo;
public:
    int findRotateSteps(string ring, string key) {
        n = ring.size();
        pos.resize(26);
        memo = vector<vector<int>> (101, vector<int>(101, INT_MAX));
        for(int i = 0; i < ring.size(); i++)
            pos[ring[i]-'a'].push_back(i);
        return dfs(key, 0, 0, 0);
    }
    int dfs(string& key, int start, int i, int step)
    {
        if(memo[start][i] != INT_MAX)
            return memo[start][i];
        if(i == key.size())
        {
            return 0;
        }
        for(int j = 0; j < pos[key[i]-'a'].size(); j++)
        {
            int delta = min(abs(start-pos[key[i]-'a'][j]), n-abs(start-pos[key[i]-'a'][j]));
            int s = dfs(key, pos[key[i]-'a'][j], i+1, 0);
            memo[start][i] = min(memo[start][i], s+delta+1);
        }
        return memo[start][i];//从start位置开始，找第 i 个字符时的最小步数
    }
};

48 ms 25.4 MB

class Solution {    //DP
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size();
        vector<vector<int>> pos(26);
        vector<vector<int>> dp(101, vector<int>(101, INT_MAX));
        for(int i = 0; i < ring.size(); i++)
            pos[ring[i]-'a'].push_back(i);
        for(int i = 0; i < key.size(); ++i)
        {
            for(int j = 0; j < pos[key[i]-'a'].size(); j++)
            {
                if(i == 0)
                {
                    int delta = min(pos[key[i]-'a'][j], n-pos[key[i]-'a'][j]);
                    dp[i][j] = min(dp[i][j], delta+1);
                }
                else
                {
                    for(int k = 0; k < pos[key[i-1]-'a'].size(); k++)
                    {   //上一个字符的状态
                        int delta = min(abs(pos[key[i-1]-'a'][k]-pos[key[i]-'a'][j]), n-abs(pos[key[i-1]-'a'][k]-pos[key[i]-'a'][j]));
                        dp[i][j] = min(dp[i][j], dp[i-1][k]+delta+1);
                    }
                }
            }
        }
        int len = key.size();
        return *min_element(dp[len-1].begin(), dp[len-1].end());
    }
};