1.题目基本信息

1.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 的下一个字符（下一阶段）, 直至完成所有拼写。

1.2.题目地址

https://leetcode.cn/problems/freedom-trail/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，预处理。统计ring中每个字符的索引数组，记为arr1；同时记n=len(ring),m=len(key)

第二步，状态定义。dp[i][j]指以用ring[j]拼写key[i]结尾的最小步数

第三步，状态初始化。dp[0][j]=min(min(j,n-j)+1 for j in range(n))

第四步，状态转移。转移方程：dp[i][j]=min(dp[i-1][k]+min(abs(j-k),n-abs(j-k))+1 for k in (k where ring[k]==key[i-1]))

第五步，最终的min(dp[m-1][j] for j in range(n) if ring[j]==key[m-1])即为题解

3.解题代码

python代码

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        # 思路：动态规划
        n = len(ring)
        m = len(key)
        # 第一步，预处理。统计ring中每个字符的索引数组，记为arr1；同时记n=len(ring),m=len(key)
        arr1 = [[] for _ in range(26)]
        for j in range(n):
            arr1[ord(ring[j]) - ord('a')].append(j)
        # 第二步，状态定义。dp[i][j]指以用ring[j]拼写key[i]结尾的最小步数
        dp = [[inf] * n for _ in range(m)]
        # 第三步，状态初始化。dp[0][j]=min(min(j,n-j)+1 for j in range(n))
        for j in range(n):
            dp[0][j] = min(dp[0][j], min(j, n - j) + 1)
        # 第四步，状态转移。转移方程：dp[i][j]=min(dp[i-1][k]+min(abs(j-k),n-abs(j-k))+1 for k in (k where ring[k]==key[i-1]))
        for i in range(1, m):
            for j in range(n):
                for k in arr1[ord(key[i - 1]) - ord('a')]:
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1)
        # 第五步，最终的min(dp[m-1][j] for j in range(n) if ring[j]==key[m-1])即为题解
        return min(dp[m - 1][j] for j in arr1[ord(key[m - 1]) - ord('a')])

c++代码

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();
        // vector<vector<int>> arr1(26, vector<int>());
        vector<int> arr1[26];
        for (int j = 0; j < n; j++) {
            arr1[ring[j] - 'a'].push_back(j);
        }
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for (int j = 0; j < n; j++) {
            dp[0][j] = min(dp[0][j], min(j, n - j) + 1);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k: arr1[key[i - 1] - 'a']) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1);
                }
            }
        }
        int result = INT_MAX;
        for (int j: arr1[key[m - 1] - 'a']) {
            result = min(result, dp[m - 1][j]);
        }
        return result;
    }
};

4.执行结果