题目描述

在电视游戏 Fallout 4 中，“通向自由之路”的请求需要玩家在一个金属拨号器通话，并使用拨号器按顺序拼出一个特殊的单词以打开自由之门。

给定一个 环形字符串，代表刻在拨号器上的代码，和另一个 特殊字符串，代表需要被拼出的单词。你需要使用 最少 的步数拨动拨号器按顺序拼出特定单词的所有字母。

初始时，环形字符串 的第一个字母在 12:00 方向，你需要通过顺时针或逆时针拨动环形拨号器使某个字母指向 12:00 方向，来一个接一个地拼出 特殊单词 的所有字母，在找到对应字母后，按动中间的按钮完成。

在转动拨号器拼写特殊字母 key[i] 的阶段：
1. 你可以每次顺时针或逆时针转动 1 次，算 1 步操作，目的是使环形字符串的某个字母指向 12:00 方向，且该字母必须等于 key[i]。
2. 如果字母 key[i] 已经在 12:00 方向，你需要按动中间的按钮拼写，这也将计算 1 步。按下之后，你才可以拼写下一个字母 （下一阶段的操作）。否则，你必须完成当前字母的拼写。

样例

输入：ring = "godding", key = "gd"
输出：4
解释：
 对于第一个字母 'g'，由于它已经在正确的位置，所以只需要 1 步（拨动按钮）拼写该字母。
 对于第二个字母 'd'，你需要逆时针转动环形字符 "gooding" 2 步使其变成 "ddinggo"。
 然后，需要 1 步完成拼写。
 所以最终输出 4。

提示

• 环形字符串和特殊单词的长度在 1 到 100 之间。
• 两个字符串仅包含小写字母，但可能含有重复的字母。
• 保证转动环形字符串可以拼出特殊单词。

算法

(动态规划) $O(nm^2)$

1. 特殊单词的长度为 $n$，环形字符串的长度记为 $m$。
2. 设状态 $f(i,j)$ 表示完成拼写特殊单词的前 $i$ 个字母，环形字符串的第 $j$ 个字母指向 12:00 方向所需要的最少步数，字符串的有效下标均从 0 开始。
3. 初始时，如果 $key[0] == ring[j]$，则 $f(0, j) = \min(j, m - j) + 1$。其余为正无穷。
4. 转移时，对于 $f(i, j)$，且当前 $key[i] == ring[j]$，枚举 $k$ 即上一次的位置，则转移 $f(i, j) = \min (f(i, j), f(i - 1, k) + \min (\left|j - k\right|, m - \left|j - k\right|) + 1)$。表示从上一个字母需要最少经过多少步到达这一个字母。注意可以顺时针或逆时针。
5. 最终答案为 $\min (f(n - 1, j))$，其中 $0 \le j < m$。

时间复杂度

• 状态数为 $O(nm)$，转移时间为 $O(m)$，故总时间复杂度为 $O(nm^2)$。

空间复杂度

• 需要额外 $O(nm)$ 的空间存储存储状态。
• 可以通过滚动数组优化到 $O(m)$。

C++ 代码

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = key.size();
        int m = ring.size();
        vector<vector<int>> f(n, vector<int>(m, INT_MAX));

        for (int j = 0; j < m; j++)
            if (key[0] == ring[j])
                f[0][j] = min(j, m - j) + 1;

        for (int i = 1; i < n; i++)
            for (int j = 0; j < m; j++)
                if (key[i] == ring[j])
                    for (int k = 0; k < m; k++)
                        if (f[i - 1][k] != INT_MAX)
                            f[i][j] = min(f[i][j],
                                    f[i - 1][k] + min(abs(j - k), m - abs(j - k)) + 1);

        int ans = INT_MAX;
        for (int j = 0; j < m; j++)
            ans = min(ans, f[n - 1][j]);

        return ans;
    }
};