LeetCode 514. 自由之路
题目描述
题意分析
圆环初始下标零朝向指针，要按
key的顺序拼出各字符。每转一格算一步，将目标字符对准后还要按一次按钮，也算一步；题目保证目标能够拼出。同一个字母可能在环上出现多次，选择哪个位置会影响下一次旋转的起点。因此每拼完一个字符，都要保留各个可能落点的最小累计代价，不能只保留当前最便宜的一条路线。
解法：DP + 预处理字符位置
核心思路
[!blue]
状态同时记录已拼字符数与指针位置。 处理key[t]之前，dpPrev[p]表示已经拼好前t个字符、环上位置p正对指针时的最少步数。若两条路线到达相同的进度和位置，后续选择完全相同，只需保留其中代价较小的一条。
pos[ch]保存字母ch在环上的全部下标，本轮只枚举等于key[t]的目标位置j。从旧位置p转到j，沿两个方向可走的距离为 $p-j $ 和 $n- p-j $，取较小值，再加一次按键。因此 dpCur[j]是所有可达p的dpPrev[p] + min(abs(p-j), n-abs(p-j)) + 1的最小值。每条拼到
j的合法路线，都必然从上一轮某个位置p转来；枚举全部来源就不会遗漏最优路线，反过来每个转移也确实完成一次合法旋转和按键。配合每个旧状态已是最优的条件，可以逐轮得到本轮的最优值。尚未拼出字符时只有下标零可达，所以
dpPrev[0] = 0，其他位置为inf。每轮先把dpCur全部重置为不可达，再计算并交换两层；旧数组只是复用存储，不能保留更早阶段的数值。全部字符完成后，最终停在哪里没有限制，取所有dpPrev中的最小值。
解题步骤
- 建立各字符在环上的位置列表。
- 初始化起点代价零，其他位置不可达。
- 逐个目标字符计算各落点的最小转动加按键代价。
- 交换两层状态，最后取最小终态。
代码实现
class Solution {
public int findRotateSteps(String ring, String key) {
int n = ring.length();
// 预处理每个字母在环上的全部下标，转移时只在这些落点之间进行。
List<List<Integer>> pos = new ArrayList<>(26);
for (int i = 0; i < 26; i++) {
pos.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
pos.get(ring.charAt(i) - 'a').add(i);
}
// 除以 4 留出余量，保证 inf 参与加法时不溢出。
int inf = Integer.MAX_VALUE / 4;
int[] dpPrev = new int[n];
int[] dpCur = new int[n];
Arrays.fill(dpPrev, inf);
// 一个字符都没拼时，指针必在下标 0，其余位置不可达。
dpPrev[0] = 0;
for (int t = 0; t < key.length(); t++) {
Arrays.fill(dpCur, inf);
int ch = key.charAt(t) - 'a';
for (int j : pos.get(ch)) {
for (int p = 0; p < n; p++) {
if (dpPrev[p] == inf) {
continue;
}
int d = Math.abs(p - j);
// 圆环上两点之间只有顺逆两条弧，长度和为 n。
int rot = Math.min(d, n - d);
int cand = dpPrev[p] + rot + 1;
if (cand < dpCur[j]) {
dpCur[j] = cand;
}
}
}
int[] tmp = dpPrev;
dpPrev = dpCur;
dpCur = tmp;
}
// 最终停在哪个位置无所谓，取所有终态的最小值。
int answer = Integer.MAX_VALUE;
for (int v : dpPrev) {
if (v < answer) {
answer = v;
}
}
return answer;
}
}
func findRotateSteps(ring string, key string) int {
n := len(ring)
// 预处理每个字母在环上的全部下标，转移时只在这些落点之间进行。
pos := make([][]int, 26)
for i := 0; i < n; i++ {
c := int(ring[i] - 'a')
pos[c] = append(pos[c], i)
}
// 除以 4 留出余量，保证 inf 参与加法时不溢出。
inf := int(^uint(0)>>1) / 4
dpPrev := make([]int, n)
dpCur := make([]int, n)
for i := 0; i < n; i++ {
dpPrev[i] = inf
}
// 一个字符都没拼时，指针必在下标 0，其余位置不可达。
dpPrev[0] = 0
for t := 0; t < len(key); t++ {
for i := 0; i < n; i++ {
dpCur[i] = inf
}
ch := int(key[t] - 'a')
for _, j := range pos[ch] {
for p := 0; p < n; p++ {
if dpPrev[p] == inf {
continue
}
d := p - j
if d < 0 {
d = -d
}
// 圆环上两点之间只有顺逆两条弧，长度和为 n。
rot := d
if n-d < rot {
rot = n - d
}
cand := dpPrev[p] + rot + 1
if cand < dpCur[j] {
dpCur[j] = cand
}
}
}
dpPrev, dpCur = dpCur, dpPrev
}
// 最终停在哪个位置无所谓，取所有终态的最小值。
answer := inf
for _, v := range dpPrev {
if v < answer {
answer = v
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(mn^2)$，其中 $m$ 为目标串长度、$n$ 为环长。每一轮至多枚举 $n$ 个目标落点，每个落点检查 $n$ 个此前位置。
- 空间复杂度：$O(n)$，位置列表与两层状态。
关键点总结
[!green]
- 落点决定下一次起转位置，不能只保留当前最小总值而丢掉位置。
- 按钮次数每个字符一次，转动为零也要按键。
- 当前层重置后再计算，避免混入更早进度的状态。
易错点总结
[!yellow]
- 每次只选最近同字符位置：局部节省可能增加后续代价。
- 所有起点状态初始化为零：相当于允许免费选择初始位置。
- 只用直线下标差：忽略圆环另一方向的更短路径。
- 最后读取交换后的旧数组：得到的不是完整 key 的结果。
- 当前字符已经对准时旋转代价为零，按键代价仍为一；只有一个环位置时，总步数就是目标串长度。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1974. 使用特殊打字机键入单词的最少时间 | 简单 | 同样在环上转到目标字符并按键，原题每个字母只有一个位置，本题重复字符导致不同落点需DP比较后续代价。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！