LeetCode 514. 自由之路

2021-03-31 HGNULB 约 12 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 514. 自由之路

题意分析

有一个刻着字母的圆环 ring，ring[0] 一开始正对 12 点方向的指针。要按顺序拼出 key，每拼一个字符需要两步：把该字符转到 12 点位置，然后按一次中心按钮。转动可以顺时针也可以逆时针，每转过一格算一步，按钮每按一次算一步。求拼完整个 key 的最少总步数。

先把代价拆干净：按钮的花费是固定的——key 有多长就要按多少次，与怎么转毫无关系。所以真正需要优化的只有转动步数，最后加上 key.length() 即可（代码里把这个 +1 分摊到每次转移里，效果一样）。

再看转动本身。圆环上从位置 p 转到位置 j，顺时针和逆时针两条路的长度之和恰好是 n，所以最小代价是 $\min( p - j ,\ n - p - j )$。这是环形结构唯一带来的额外处理，一个取 min 就解决了。

难点在于同一个字母可能在环上出现多次。拼 key[i] 时选哪一个位置，眼下的代价可能相同甚至更差，却会改变后续所有字符的起转点。这就是典型的「当前最优不等于全局最优」，贪心地每次选最近的那个必错，必须把每种落点都保留下来继续往后算。

约束 $ ring \le 100$、$ key \le 100$ 极小，明确允许 $O( key \cdot n^2)$ 这一量级（约 $10^6$）的做法，等于直接暗示「以字符下标 × 环上位置为状态、逐字符递推」是被期待的解法。

边界：题目保证 key 中每个字符必然在 ring 中出现，所以不存在无解；起点固定在下标 0 而不是任意位置；key 中相邻字符相同时，转动代价为 0 但按钮仍要按。

解法：DP + 预处理字符位置

核心思路

暴力做法是搜索：拼第 i 个字符时，枚举它在环上的每个出现位置，递归下去。设某个字母平均出现 c 次，搜索树规模就是 $c^{\lvert key\rvert}$，指数级，ring = "aaaa...a" 这种输入直接爆炸。

观察搜索树上的重复：走到「已经拼完 key 的前 i 个字符，指针此刻停在环上位置 j」这个局面时，后续的最优代价只取决于 i 和 j 这两个量，跟前面是怎么绕过来的一点关系都没有。既然如此，同一个 (i, j) 被不同路径反复求解就是纯粹的浪费——把它记下来，指数级搜索立刻塌缩成多项式级递推。

于是定义 dp[i][j] = 已经拼完 key 的前 i 个字符、且指针当前停在环上下标 j 时，所花的最小总步数（含已按下的 i 次按钮）。这个定义里，j 必须是 key[i - 1] 出现的位置之一，否则状态无意义。

转移：dp[i][j] = min over p ( dp[i-1][p] + rot(p, j) ) + 1，其中 p 遍历 key[i - 2] 的所有出现位置（i = 1 时 p 只能是起点 0），rot(p, j) = min(|p - j|, n - |p - j|)。含义就是：从上一步的任意落点转到本次落点，取所有走法里最省的，再加一次按键。

初始状态 dp[0][0] = 0、其余为无穷大——一个字符都没拼时指针必在下标 0，别的位置不可达。答案是 dp[|key|][*] 中的最小值：最后停在哪个位置无所谓，只要字符拼对了。

还有一个关键的预处理。转移时需要快速拿到「某个字母在环上的全部下标」，每次现扫一遍 ring 是 $O(n)$ 的浪费。开一个长度 26 的桶，pos[c] 存字母 c 的所有下标，一次遍历建好，之后 $O(1)$ 取用。这样 dpCur 只在真正合法的落点上被赋值，其余位置保持无穷大，天然表达了「不可达」。

由于 dp[i] 只依赖 dp[i-1]，第一维可以用两个一维数组滚动，空间从 $O(\lvert key\rvert \cdot n)$ 压到 $O(n)$。

正确性可按 key 前缀长度归纳：初态只允许指针位于 0；假设上一层记录了到所有合法落点的最小代价，本层枚举每个目标字符位置和全部可达前驱，转移取二者环形最短距离，因此得到本层每个落点的最优值。最后对所有落点取最小值，就是完整 key 的全局最优解。

解题步骤

建 26 个位置列表，扫一遍 ring 把每个下标放入对应字母的列表。后面可直接枚举目标字符的合法落点，不必重复扫描整个环。

准备 dpPrev、dpCur 两个长度为 n 的数组，dpPrev 全填一个大数 inf，再把 dpPrev[0] = 0。为什么：inf 表示状态不可达；取 Integer.MAX_VALUE / 4 而不是 MAX_VALUE，是为了让 inf + rot + 1 这种加法不溢出。dpPrev[0] = 0 编码了「一个字符都没拼、指针在起点、代价为 0」这个唯一合法初态。

外层按 t 遍历 key 的每个字符，每轮先把 dpCur 全部重置为 inf。为什么：dpCur 是滚动复用的旧数组，残留的上上轮数据会污染本轮的 min；重置成 inf 相当于声明「本轮所有位置默认不可达」。

内层枚举本轮字符的每个落点 j（来自 pos[ch]），再枚举上一轮的每个位置 p。为什么：落点 j 必须是本轮字符实际出现的下标，否则转过去也按不出正确字符；对 p 全量枚举是因为上一轮可能停在多个位置，必须挑出总代价最小的来源。

dpPrev[p] == inf 时直接跳过。为什么：不可达的来源不能作为转移起点；跳过既保证正确性，也顺带避免了 inf 参与加法。实际上不为 inf 的 p 只有上一个字符的出现位置，这个判断把内层循环的有效次数压到了上一字符的出现次数。

计算 d = |p - j|，取 rot = min(d, n - d)，用 dpPrev[p] + rot + 1 更新 dpCur[j] 的最小值。为什么：d 是顺时针（或逆时针）的一段弧长，n - d 是另一段，圆环上两点间必然只有这两条路；+1 是本次按键，把它放在转移里可以省掉最后统一加 key.length() 的步骤。

本轮结束后交换 dpPrev 与 dpCur。为什么：下一轮的「上一层」就是本轮结果；交换而非拷贝，是 $O(1)$ 的滚动。

全部字符处理完后，返回 dpPrev 中的最小值。为什么：key 已拼完，指针最终停在哪里题目并不关心，所以在所有终态里取最优。注意此时结果在 dpPrev 而不是 dpCur，因为最后一轮末尾刚做过交换。

以 ring = "godding", key = "gd" 走一遍（n = 7，下标 0..6 依次是 g o d d i n g）。预处理得 pos['g'] = [0, 6]、pos['o'] = [1]、pos['d'] = [2, 3]、pos['i'] = [4]、pos['n'] = [5]。初始 dpPrev = [0, inf, inf, inf, inf, inf, inf]。

第一轮 t = 0，字符 g，落点为 0 和 6。落点 j = 0：唯一可达的 p = 0，d = 0，rot = 0，dpCur[0] = 0 + 0 + 1 = 1。落点 j = 6：p = 0，d = 6，rot = min(6, 1) = 1（逆时针走一格更近），dpCur[6] = 0 + 1 + 1 = 2。交换后 dpPrev[0] = 1、dpPrev[6] = 2，其余 inf。

第二轮 t = 1，字符 d，落点为 2 和 3。落点 j = 2：从 p = 0 来，d = 2，rot = 2，得 1 + 2 + 1 = 4；从 p = 6 来，d = 4，rot = min(4, 3) = 3，得 2 + 3 + 1 = 6；取最小 dpCur[2] = 4。落点 j = 3：从 p = 0 来 rot = 3，得 1 + 3 + 1 = 5；从 p = 6 来 d = 3，rot = 3，得 2 + 3 + 1 = 6；取 dpCur[3] = 5。

交换后在 dpPrev 中取最小值得 4，即答案。不能据此贪心地只保留当前最近落点：例如 ring = "aaabacc"、key = "cab"，最近路线依次走 6 → 0 → 3，转动 5 步、总计 8 步；选择稍远的下标 5 后走 5 → 4 → 3，只转动 4 步、总计 7 步。当前多花一步可能为后续省下更多，所以所有落点都要保留。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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(\lvert key\rvert \cdot n^2)$。外层遍历 key，每轮当前落点和上一层落点最坏各有 n 个；实际只对可达前驱执行转移。

空间复杂度：$O(n)$。两个滚动数组和位置桶都与 ring 长度同阶；完整二维表则需要 $O(\lvert key\rvert \cdot n)$。

关键点总结

「同一个目标字符有多个落点，选哪个会影响后续」是识别本题需要 DP 而非贪心的信号。凡是当前决策改变后续状态起点、且代价不可分离时，都要把每种落点作为状态保留。

状态定义必须把「进度」和「位置」两件事都编码进去：dp[已拼字符数][当前指针位置]。少任何一维都会导致无法转移或状态混淆，面试时先把这行定义写在白板上再动手。

固定代价要早点剥离。按键次数恒为 |key|，与转法无关，认清这点后问题就只剩纯粹的转动优化，思路立刻清爽。

环形距离统一写成 $\min(d,\ n - d)$，是所有圆环题的标准零件，比手写顺逆两套逻辑更不容易错。

用「按字符建位置桶」做预处理，是把稀疏转移从 $O(n)$ 扫描降到 $O(1)$ 查表的通用技巧，在字符串类 DP 中反复出现。

DP 只依赖上一层时用双数组滚动，交换指针而不是拷贝数组，空间降一维、时间不变。

易错点总结

贪心地每次转到最近的同名字符：ring = "aaabacc", key = "cab" 时最近路线 6 → 0 → 3 需要 8 步，而全局最优路线 5 → 4 → 3 只需 7 步。

dpPrev 初始化时忘了把 dpPrev[0] = 0：全为 inf → 第一轮所有 p 都被 continue 跳过，dpCur 全是 inf，最终返回一个巨大的无意义数字。

dpPrev 初始化成全 0 而不是全 inf：ring = "ab", key = "b" → 会认为指针一开始可以停在下标 1，直接得出 1 步，而正确答案是转 1 格再按共 2 步。

每轮忘记把 dpCur 重置为 inf：滚动数组里残留着上上轮的值 → 某个本轮不可达的位置带着旧代价参与后续 min，结果偏小且随 key 长度无规律地错。

环形距离只写 Math.abs(p - j)：ring = "godding", key = "g" 走到落点 6 时会算成 6 步而不是 1 步，凡是跨越环首尾的最优路线全部丢失。

落点不限定在 pos[ch] 而是遍历全部 n 个位置：会把指针停在字符不匹配的位置也当作合法状态，等于允许「按出错误字符」，答案偏小。

最后返回 dpCur 的最小值：末轮循环尾部刚交换过指针，dpCur 存的是上一层数据 → key = "gd" 会返回拼完 g 时的代价 1，而不是 4。

最后返回 dpPrev[0]：强行要求指针回到起点 → ring = "godding", key = "gd" 时 dpPrev[0] 是 inf，返回天文数字。

用 Integer.MAX_VALUE 当 inf 且不做 continue 跳过：dpPrev[p] + rot + 1 溢出成负数 → 负值赢下 min，dpCur 被污染成负数，答案彻底错乱。

忘记加每次按键的 +1：只统计了转动步数 → ring = "godding", key = "gd" 返回 2，比正确答案少了恰好 |key|。

相似题目

题目	难度	考察点
72. 编辑距离	中等	同为「按字符推进 + 二维状态」，但第二维是另一个串的进度而非环上位置
918. 环形子数组的最大和	中等	同样是环形结构，但用「总和减最小子数组」绕开环，而不是取两段弧的最小值
213. 打家劫舍 II	中等	环形约束通过「拆成两条线性链各跑一遍」化解，是处理环的另一套通用手法
741. 摘樱桃	困难	状态里同时装两个位置维度，比本题多一维，转移要枚举四种走法组合
787. K 站中转内最便宜的航班	中等	同为「层数 × 节点」的分层最短路，只是层数上限由题目给定而非串长
1631. 最小体力消耗路径	中等	代价函数是路径上的最大值而非累加和，因此要用二分或并查集而非线性 DP
312. 戳气球	困难	决策同样影响后续局面，但区间之间互相牵连，必须按区间长度而非位置递推
面试题 16.20. T9键盘	中等	同为按键与字符的多对多映射，但只需前缀匹配枚举，不涉及位置代价优化