What is the best approach to solve Freedom Trail?

Use state transition dynamic programming to track minimum steps for each key character while considering all positions on the ring.

How do I calculate rotation steps efficiently?

Compute both clockwise and anticlockwise distances between current and target positions, then add one step for pressing the button.

Can characters appear multiple times on the ring?

Yes, and preprocessing all indices of each character allows DP to select the minimal rotation path for every key character.

What is the time complexity of the optimal solution?

It is O(RK * log(RK)), where R is ring length and K is key length, because each DP transition considers all positions with minimal rotation.

Why is this problem called a state transition DP pattern?

Because the solution tracks the minimal steps for each key character while transitioning between all feasible ring positions, typical of state transition dynamic programming.

#514

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

自由之路

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “ Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数…

字符串动态规划深度优先搜索广度优先搜索

题目描述

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 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 <= 100
ring 和 key 只包含小写英文字母
保证字符串 key 一定可以由字符串 ring 旋转拼出

lightbulb

解题思路

方法一：动态规划

我们首先预处理出字符串 $ring$ 中每个字符 $c$ 出现的位置列表，记录在数组 $pos[c]$ 中。不妨假设字符串 $key$ 和 $ring$ 的长度分别为 $m$ 和 $n$ 。

然后我们定义 $f[i][j]$ 表示拼写完字符串 $key$ 的前 $i+1$ 个字符，且 $ring$ 的第 $j$ 个字符与 $12:00$ 方向对齐的最少步数。初始时 $f[i][j]=+\infty$ 。答案为 $\min_{0 \leq j < n} f[m - 1][j]$ 。

我们可以先初始化 $f[0][j]$ ，其中 $j$ 是字符 $key[0]$ 在 $ring$ 中出现的位置。由于 $ring$ 的第 $j$ 个字符与 $12:00$ 方向对齐，因此我们只需要 $1$ 步即可拼写出 $key[0]$ 。此外，我们还需要 $min(j, n - j)$ 步将 $ring$ 旋转到 $12:00$ 方向。因此 $f[0][j]=min(j, n - j) + 1$ 。

接下来，我们考虑当 $i \geq 1$ 时，状态如何转移。我们可以枚举 $key[i]$ 在 $ring$ 中的位置列表 $pos[key[i]]$ ，并枚举 $key[i-1]$ 在 $ring$ 中的位置列表 $pos[key[i-1]]$ ，然后更新 $f[i][j]$ ，即 $f[i][j]=\min_{k \in pos[key[i-1]]} f[i-1][k] + \min(\textit{abs}(j - k), n - \textit{abs}(j - k)) + 1$ 。

最后，我们返回 $\min_{0 \leq j \lt n} f[m - 1][j]$ 即可。

时间复杂度 $O(m \times n^2)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $key$ 和 $ring$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        m, n = len(key), len(ring)
        pos = defaultdict(list)
        for i, c in enumerate(ring):
            pos[c].append(i)
        f = [[inf] * n for _ in range(m)]
        for j in pos[key[0]]:
            f[0][j] = min(j, n - j) + 1
        for i in range(1, m):
            for j in pos[key[i]]:
                for k in pos[key[i - 1]]:
                    f[i][j] = min(
                        f[i][j], f[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1
                    )
        return min(f[-1][j] for j in pos[key[-1]])

speed

复杂度分析

指标	值
时间	complexity is O(RK * log(RK)) due to iterating over ring positions for each key character and computing minimal rotations. Space complexity is O(R * K) to store DP states for all ring indices and key positions.
空间	O(R \cdot K)

psychology

面试官常问的追问

外企场景

question_mark
Look for proper DP state definition and transitions when the candidate writes code.
question_mark
Check if the candidate optimizes rotations both clockwise and anticlockwise.
question_mark
Confirm the solution avoids recomputation by correctly mapping characters to multiple positions.

warning

常见陷阱

外企场景

error
Failing to account for both clockwise and anticlockwise rotation distances.
error
Not preprocessing ring characters to multiple indices, causing slow transitions.
error
Incorrectly initializing DP states leading to overcounting steps or misaligned characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow a ring with repeated characters but a longer key to test DP efficiency.
arrow_right_alt
Consider a key that includes characters not in the initial 12:00 alignment to stress rotations.
arrow_right_alt
Use a ring of maximum length (100) and a key with maximum length (100) to evaluate space optimization.

help

常见问题

外企场景

继续练习

#488 祖玛游戏 #472 连接词 #449 序列化和反序列化二叉搜索树