Hard
题目描述
在电子游戏"辐射4"中，任务"自由之路"要求玩家到达一个叫做"自由之路环"的金属表盘，并使用该表盘拼写特定的关键词来开门。
给你一个字符串 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 <= 100ring和key只包含小写英文字母- 保证 字符串
key一定可以由字符串ring旋转拼出
解题思路
这道题可以用动态规划来解决。
思路分析：
对于每个需要拼写的字符 key[i]，我们需要考虑从当前位置旋转到 ring 中任意一个匹配字符的最小代价。
我们可以定义 dp[i][j] 表示拼写完 key 的前 i 个字符，且当前 ring 的指针位于位置 j 时的最小步数。
状态转移：
- 对于每个
key[i]，找到ring中所有等于key[i]的位置 - 对于每个这样的位置
next_pos，计算从所有可能的前一个位置prev_pos到next_pos的旋转代价 - 旋转代价为：
min(顺时针距离, 逆时针距离) - 加上按按钮的1步，更新
dp[i+1][next_pos]
优化：
- 预处理每个字符在
ring中出现的所有位置，避免重复查找 - 计算两点间的最短旋转距离：
min(abs(a-b), n-abs(a-b))
时间复杂度：O(m×n²)，其中 m 是 key 的长度，n 是 ring 的长度。 空间复杂度：O(m×n)。
代码实现
class Solution {
public:
int findRotateSteps(string ring, string key) {
int n = ring.length();
int m = key.length();
// 预处理：记录每个字符在ring中的所有位置
vector<vector<int>> pos(26);
for (int i = 0; i < n; i++) {
pos[ring[i] - 'a'].push_back(i);
}
// dp[i][j] 表示拼写完key的前i个字符，当前指针在位置j的最小步数
vector<vector<int>> dp(m + 1, vector<int>(n, INT_MAX));
dp[0][0] = 0; // 初始状态：指针在位置0
for (int i = 0; i < m; i++) {
int ch = key[i] - 'a';
for (int j = 0; j < n; j++) {
if (dp[i][j] == INT_MAX) continue;
// 尝试转到所有包含key[i]字符的位置
for (int next_pos : pos[ch]) {
// 计算从位置j到next_pos的最小旋转步数
int dist = min(abs(j - next_pos), n - abs(j - next_pos));
dp[i + 1][next_pos] = min(dp[i + 1][next_pos], dp[i][j] + dist + 1);
}
}
}
// 找到拼写完所有字符的最小步数
int result = INT_MAX;
for (int j = 0; j < n; j++) {
result = min(result, dp[m][j]);
}
return result;
}
};
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
# 预处理：记录每个字符在ring中的所有位置
from collections import defaultdict
pos = defaultdict(list)
for i, ch in enumerate(ring):
pos[ch].append(i)
# dp[i][j] 表示拼写完key的前i个字符，当前指针在位置j的最小步数
dp = [[float('inf')] * n for _ in range(m + 1)]
dp[0][0] = 0 # 初始状态：指针在位置0
for i in range(m):
ch = key[i]
for j in range(n):
if dp[i][j] == float('inf'):
continue
# 尝试转到所有包含key[i]字符的位置
for next_pos in pos[ch]:
# 计算从位置j到next_pos的最小旋转步数
dist = min(abs(j - next_pos), n - abs(j - next_pos))
dp[i + 1][next_pos] = min(dp[i + 1][next_pos], dp[i][j] + dist + 1)
# 找到拼写完所有字符的最小步数
return min(dp[m])
public class Solution {
public int FindRotateSteps(string ring, string key) {
int n = ring.Length;
int m = key.Length;
// 预处理：记录每个字符在ring中的所有位置
var pos = new List<int>[26];
for (int i = 0; i < 26; i++) {
pos[i] = new List<int>();
}
for (int i = 0; i < n; i++) {
pos[ring[i] - 'a'].Add(i);
}
// dp[i][j] 表示拼写完key的前i个字符，当前指针在位置j的最小步数
var dp = new int[m + 1, n];
for (int i = 0; i <= m; i++) {
for (int j = 0; j < n; j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0; // 初始状态：指针在位置0
for (int i = 0; i < m; i++) {
int ch = key[i] - 'a';
for (int j = 0; j < n; j++) {
if (dp[i, j] == int.MaxValue) continue;
// 尝试转到所有包含key[i]字符的位置
foreach (int nextPos in pos[ch]) {
// 计算从位置j到nextPos的最小旋转步数
int dist = Math.Min(Math.Abs(j - nextPos), n - Math.Abs(j - nextPos));
dp[i + 1, nextPos] = Math.Min(dp[i + 1, nextPos], dp[i, j] + dist + 1);
}
}
}
// 找到拼写完所有字符的最小步数
int result = int.MaxValue;
for (int j = 0; j < n; j++) {
result = Math.Min(result, dp[m, j]);
}
return result;
}
}
var findRotateSteps = function(ring, key) {
const n = ring.length;
const m = key.length;
const charPositions = new Map();
for (let i = 0; i < n; i++) {
if (!charPositions.has(ring[i])) {
charPositions.set(ring[i], []);
}
charPositions.get(ring[i]).push(i);
}
const memo = new Map();
function dp(pos, keyIndex) {
if (keyIndex === m) return 0;
const key_str = `${pos},${keyIndex}`;
if (memo.has(key_str)) return memo.get(key_str);
const targetChar = key[keyIndex];
const positions = charPositions.get(targetChar);
let minSteps = Infinity;
for (const targetPos of positions) {
const clockwise = (targetPos - pos + n) % n;
const anticlockwise = (pos - targetPos + n) % n;
const steps = Math.min(clockwise, anticlockwise) + 1 + dp(targetPos, keyIndex + 1);
minSteps = Math.min(minSteps, steps);
}
memo.set(key_str, minSteps);
return minSteps;
}
return dp(0, 0);
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(m×n²) | m为key长度，n为ring长度。对于每个key字符，需要考虑从所有ring位置转移到所有匹配位置 |
| 空间复杂度 | O(m×n) | DP数组的大小为(m+1)×n，预处理位置信息的空间为O(n) |