0514. Freedom Trail

题目信息

题号:

0514

难度:

Hard

主题:

环形拨盘、顺逆时针旋转、逐字符拼写、最少操作

原题:

LeetCode 0514

重点:

拨盘首字符初始位于正上方、每次旋转一格算一步、按键确认也算一步、同一字符可能有多个位置

题目重述

一个环形拨盘由字符串 ring 表示,字符按圆周顺序排列,开始时 ring[0] 位于正上方。需要依次拼写字符串 key 中的每个字符。

每一步可以将拨盘顺时针或逆时针旋转一个位置;当目标字符位于正上方时,还必须按下中心按钮一次来确认该字符。返回拼完整个 key 所需的最少总步数,旋转和按键都计入。题目保证 key 中的每个字符都存在于 ring 中。

自建示例

同一字符有多个可选位置:

输入:ring = "abca",key = "ca"
输出:5
解释:从位置 0 的 a 旋转两格到 c 并按键,共 3 步;随后旋转一格到位置 3 的 a 并按键,共 2 步,总计 5 步。

无需旋转即可连续确认:

输入:ring = "xyz",key = "xx"
输出:2
解释:x 初始就在正上方,两次字符确认各按键一次,不需要旋转。

状态是“当前指针位置 + 已拼写前缀”

同一个字符可能在拨盘上出现多次,不能只记录字符本身;完成某个前缀后,指针停在哪个位置会影响下一个字符的旋转距离。令 dp[i] 表示处理完当前前缀且指针位于 ring[i] 的最少步数,只在目标字符出现的位置之间转移。

从位置 i 到 j 的最短旋转距离为 min(|i-j|, r-|i-j|),每次转移再加一次确认按钮。初始状态是位置 0,答案取最后一个字符所有候选位置的最小值。

C++ 实现

class Solution {
public:
    int findRotateSteps(std::string ring, std::string key) {
        int size = static_cast<int>(ring.size());
        std::vector<std::vector<int>> positions(26);
        for (int i = 0; i < size; ++i) {
            positions[ring[i] - 'a'].push_back(i);
        }

        const int infinity = 1e9;
        std::vector<int> dp(size, infinity);
        dp[0] = 0;
        for (char target : key) {
            std::vector<int> 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)。