0514. Freedom Trail =================== 题目信息 -------- :题号: 0514 :难度: Hard :主题: 环形拨盘、顺逆时针旋转、逐字符拼写、最少操作 :原题: `LeetCode 0514 `_ :重点: 拨盘首字符初始位于正上方、每次旋转一格算一步、按键确认也算一步、同一字符可能有多个位置 题目重述 -------- 一个环形拨盘由字符串 ``ring`` 表示,字符按圆周顺序排列,开始时 ``ring[0]`` 位于正上方。需要依次拼写字符串 ``key`` 中的每个字符。 每一步可以将拨盘顺时针或逆时针旋转一个位置;当目标字符位于正上方时,还必须按下中心按钮一次来确认该字符。返回拼完整个 ``key`` 所需的最少总步数,旋转和按键都计入。题目保证 ``key`` 中的每个字符都存在于 ``ring`` 中。 自建示例 -------- 同一字符有多个可选位置: .. code-block:: text 输入:ring = "abca",key = "ca" 输出:5 解释:从位置 0 的 a 旋转两格到 c 并按键,共 3 步;随后旋转一格到位置 3 的 a 并按键,共 2 步,总计 5 步。 无需旋转即可连续确认: .. code-block:: text 输入:ring = "xyz",key = "xx" 输出:2 解释:x 初始就在正上方,两次字符确认各按键一次,不需要旋转。 状态是“当前指针位置 + 已拼写前缀” ---------------------------------- 同一个字符可能在拨盘上出现多次,不能只记录字符本身;完成某个前缀后,指针停在哪个位置会影响下一个字符的旋转距离。令 ``dp[i]`` 表示处理完当前前缀且指针位于 ``ring[i]`` 的最少步数,只在目标字符出现的位置之间转移。 从位置 ``i`` 到 ``j`` 的最短旋转距离为 ``min(|i-j|, r-|i-j|)``,每次转移再加一次确认按钮。初始状态是位置 0,答案取最后一个字符所有候选位置的最小值。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findRotateSteps(std::string ring, std::string key) { int size = static_cast(ring.size()); std::vector> positions(26); for (int i = 0; i < size; ++i) { positions[ring[i] - 'a'].push_back(i); } const int infinity = 1e9; std::vector dp(size, infinity); dp[0] = 0; for (char target : key) { std::vector next(size, infinity); for (int from = 0; from < size; ++from) { if (dp[from] == infinity) continue; for (int to : positions[target - 'a']) { int distance = std::abs(from - to); distance = std::min(distance, size - distance); next[to] = std::min(next[to], dp[from] + distance + 1); } } dp.swap(next); } return *std::min_element(dp.begin(), dp.end()); } }; 代码分析 -------- 每个状态都保留了下一步所需的完整位置信息,转移枚举所有同字符位置,因此不会错过更近或更远但能改善后续的选择。设拨盘长度为 ``r``、目标长度为 ``m``,时间复杂度为 ``O(mr^2)`` 的上界,空间复杂度为 ``O(r)``。