514. Freedom Trail
514. Freedom Trail
🔴 🔖 深度优先搜索
广度优先搜索
字符串
动态规划
🔗 LeetCode
题目
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 to open the door.
Given a string ring
that represents the code engraved on the outer ring and another string key
that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at the "12:00"
direction. You should spell all the characters in key
one by one by rotating ring
clockwise or anticlockwise to make each character of the string key aligned at the "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 by one place, which counts as one step. The final purpose of the rotation is to align one of
ring
's characters at the"12:00"
direction, where this character must equalkey[i]
. - If the character
key[i]
has been aligned at the"12:00"
direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.
Example 1:
![](https://assets.leetcode.com/uploads/2018/10/22/ring.jpg)
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.
Example 2:
Input: ring = "godding", key = "godding"
Output: 13
Constraints:
1 <= ring.length, key.length <= 100
ring
andkey
consist of only lower case English letters.- It is guaranteed that
key
could always be spelled by rotatingring
.
题目大意
电子游戏“辐射 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
的下一个字符(下一阶段), 直至完成所有拼写。
示例 1:
![](https://assets.leetcode.com/uploads/2018/10/22/ring.jpg)
输入: ring = "godding", key = "gd"
输出: 4
解释:
对于 key 的第一个字符 'g',已经在正确的位置, 我们只需要 1 步来拼写这个字符。
对于 key 的第二个字符 'd',我们需要逆时针旋转 ring "godding" 2 步使它变成 "ddinggo"。
当然, 我们还需要 1 步进行拼写。
因此最终的输出是 4。
示例 2:
输入: ring = "godding", key = "godding"
输出: 13
提示:
1 <= ring.length, key.length <= 100
ring
和key
只包含小写英文字母- 保证 字符串
key
一定可以由字符串ring
旋转拼出
解题思路
构建映射:首先构建一个映射
map
,将每个字符在ring
中的出现位置记录下来。动态规划递归:使用递归的方式进行动态规划。定义一个二维数组
dp
,其中dp[i][j]
表示指针在ring[i]
时,到key[j]
最少需要几步操作。递归函数:定义递归函数
helper(i, j)
,表示当指针在ring[i]
位置,需要匹配key[j]
时的最小操作步数。递归结束条件:当
j
等于n
时,表示已经匹配完整个key
字符串,返回 0。递归过程:遍历
key[j]
对应的所有可能位置k
,计算旋转次数rotate
,然后递归调用helper(k, j + 1)
,加上当前的旋转次数和 1,取最小值作为结果。记忆化搜索:为了避免重复计算,使用数组
dp
进行记忆化搜索,记录已经计算过的状态。
- 时间复杂度:
O(m * n)
- 其中m
是ring
的长度,n
是key
的长度。对于key
中的每个字符,都会考虑ring
中的所有可能位置。 - 空间复杂度:
O(m * n)
- 使用了一个二维数组来存储中间状态。
代码
/**
* @param {string} ring
* @param {string} key
* @return {number}
*/
var findRotateSteps = function (ring, key) {
const m = ring.length;
const n = key.length;
const map = new Map();
// 构建映射
for (let i = 0; i < m; i++) {
let temp = map.get(ring[i]) || [];
temp.push(i);
map.set(ring[i], temp);
}
// 初始化动态规划数组
const dp = new Array(m).fill(0).map(() => new Array(n).fill(-1));
// 定义递归函数
const helper = (i, j) => {
// 递归结束条件
if (j == n) return 0;
// 记忆化搜索
if (dp[i][j] !== -1) return dp[i][j];
let res = Infinity;
// 遍历 key[j] 对应的所有可能位置
for (let k of map.get(key[j])) {
// 计算旋转表盘次数
const rotate = Math.min(Math.abs(k - i), m - Math.abs(k - i));
// 递归调用,加上当前的旋转次数和 1,取最小值
res = Math.min(res, 1 + rotate + helper(k, j + 1));
}
dp[i][j] = res;
return res;
};
// 返回结果
return helper(0, 0);
};