0-1最短路/记忆化搜索,LeetCode 514. 自由之路

一、题目

1、题目描述

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

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

2、接口描述

​

class Solution {
public:
    int findRotateSteps(string ring, string key) {

    }
};

3、原题链接

514. 自由之路

二、解题报告

1、思路分析

今天看到题就觉得是一个最短路问题，为什么这样想呢？

我们要按顺序将转盘转到key的对应字符，等于说一条路径上的节点是确定的，让我们规划相邻两个点之间如何抵达，使得路径总长度最短。

那么我们让相邻两个点以最短方式抵达即可。

根据题意，我们转动一次可以看作花费1点路径长度，那这个图就变成了0-1最短路问题，对于0-1最短路用bfs将图遍历一遍就能完成。

那么这个图如何建立呢？

设len(ring) = n , len(key) = m，我们建立一个n x m的网格，那么我们初始是在（0，0）的位置，最终要到达（i，m-1），i看似不确定，由于初始位置是0，其实i是确定的

我们用bfs在这个网格上跑最短路即可（详细看代码，很容易理解）。

但是我们发现效率不是很高！

想了一下，我们最短路是确定的，但是跑最短路的过程中遍历了很多无效路径，所以可以优化。

我们上面可以看作是当前指针指向ring[0]，要拨动到的字符为key[0]，最终拨动到key[m-1]的最短路径，那么初始状态，我们如果ring[0] = key[0]，那么直接看key[1]，否则我们就要拨动到key[1]的位置，显然要找最短的

也就是说，每一步我们都要直到当前指针字符左右最近的key[j]的位置

所以我们预处理出left[i][ch]和right[i][ch]，代表ring[i]左右最近的ch的下标

然后设计dfs(i,j)为当前指向i，key对应j，要抵达key[m - 1]的最短拨动次数

那么

dfs(i,j) = dfs(i , j + 1)，ring[i] = key[j]

dfs(i,j) = min(L1 + dfs(l , j) , L2 + dfs(r , j))，ring[i] != key[j]

由于求的是拨动次数，还要加上m个按键次数，所以最终答案就是dfs(0, 0)  + m

避免了很多无效状态所以效率远高于bfs，虽然时间复杂度差不多，但是后者实际中远达不到上限

2、复杂度

bfs: 时间复杂度： O(nm) 空间复杂度：O(nm)

记忆化搜索:时间复杂度： O(n(U + m)) 空间复杂度：O(n(U + m))

3、代码详解

​bfs最短路

class Solution {
public:
    typedef pair<int, int> pii;
    bool vis[105][105];
    pii q[10010];
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        memset(vis, 0, sizeof(vis));
        int f = 0 , b = 0;
        q[f++] = {0, 0}, vis[0][0] = 1;
        for(int dis = 0; ; dis++)
        {
            for (int ed = f; b < ed; b++)
            {
                auto [x, y] = q[b];
                if (y == m) return dis;
                if (ring[x] == key[y]) {
                    if (!vis[x][y + 1])
                        vis[x][y + 1] = 1, q[f++] = {x, y + 1};
                    continue;
                }
                for (auto j : {(x - 1 + n) % n, (x + 1) % n})
                    if (!vis[j][y])
                        vis[j][y] = 1, q[f++] = {j, y};
            }
        }
        return -1;
    }
};

记忆化搜索

class Solution {
public:
int f[105][105], left[105][26], right[105][26], pos[26];
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        memset(f, -1, sizeof(f));
        // 预处理s[i]左右最近的a~z
        for(int i = 0; i < n; i++)
            pos[ring[i] - 'a'] = i;
        for(int i = 0; i < n; i++)
            memcpy(left[i], pos, sizeof(pos)), pos[ring[i] - 'a'] = i;
        for(int i = n - 1; i >= 0; i--)
            pos[ring[i] - 'a'] = i;
        for(int i = n - 1; i >= 0; i--)
            memcpy(right[i], pos, sizeof(pos)), pos[ring[i] - 'a'] = i;

        function<int(int,int)> dfs = [&](int i, int j)->int{
            if(j == m) return 0;
            if(~f[i][j]) return f[i][j];
            
            int& res = f[i][j];
            char ch = key[j];
            
            if(ring[i] == ch) return res = dfs(i, j + 1);

            int l = left[i][ch - 'a'], r = right[i][ch - 'a'];
            return res = min((l > i ? n - l + i : i - l) + dfs(l, j + 1) ,
            (r < i ? n - i + r : r - i) + dfs(r, j + 1));
        };
        return m + dfs(0, 0);
    }
};