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]:

1. 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 equal key[i].
2. 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:

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 and key consist of only lower case English letters.
• It is guaranteed that key could always be spelled by rotating ring.

题目大意

电子游戏“辐射 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：

输入: 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 旋转拼出

解题思路

1. 构建映射：首先构建一个映射 map，将每个字符在 ring 中的出现位置记录下来。

2. 动态规划递归：使用递归的方式进行动态规划。定义一个二维数组 dp，其中 dp[i][j] 表示指针在 ring[i] 时，到 key[j] 最少需要几步操作。

3. 递归函数：定义递归函数 helper(i, j)，表示当指针在 ring[i] 位置，需要匹配 key[j] 时的最小操作步数。

4. 递归结束条件：当 j 等于 n 时，表示已经匹配完整个 key 字符串，返回 0。

5. 递归过程：遍历 key[j] 对应的所有可能位置 k，计算旋转次数 rotate，然后递归调用 helper(k, j + 1)，加上当前的旋转次数和 1，取最小值作为结果。

6. 记忆化搜索：为了避免重复计算，使用数组 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);
};