自由之路

难度: Hard

电子游戏“辐射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 旋转拼出

Submission

运行时间: 41 ms

内存: 0.0 MB

# https://space.bilibili.com/206214
class Solution:
    def findRotateSteps(self, s: str, t: str) -> int:
        s = [ord(c) - ord('a') for c in s]
        t = [ord(c) - ord('a') for c in t]
        n, m = len(s), len(t)

        # 先算出每个字母的最后一次出现的下标
        # 由于 s 是环形的，循环结束后的 pos 就刚好是 left[0]
        pos = [0] * 26  # 初始值不重要
        for i, c in enumerate(s):
            pos[c] = i
        # 计算每个 s[i] 左边 a-z 的最近下标（左边没有就从 n-1 往左找）
        left = [None] * n
        for i, c in enumerate(s):
            left[i] = pos[:]
            pos[c] = i  # 更新下标

        # 先算出每个字母的首次出现的下标
        # 由于 s 是环形的，循环结束后的 pos 就刚好是 right[n-1]
        pos = [0] * 26  # 初始值不重要
        for i in range(n - 1, -1, -1):
            pos[s[i]] = i
        # 计算每个 s[i] 右边 a-z 的最近下标（左边没有就从 0 往右找）
        right = [None] * n
        for i in range(n - 1, -1, -1):
            right[i] = pos[:]
            pos[s[i]] = i  # 更新下标

        pos = [[] for _ in range(26)]
        for i, b in enumerate(s):
            pos[b].append(i)

        f = [0] * n
        for j in range(m - 1, 0, -1):
            c = t[j]
            if c == t[j - 1]:
                continue
            nf = [0] * n
            for i in pos[t[j - 1]]:
                l, r = left[i][c], right[i][c]
                res1 = f[l] + (n - l + i if l > i else i - l)
                res2 = f[r] + (n - i + r if r < i else r - i)
                if res2 < res1 : res1 = res2
                nf[i] = res1          
            f = nf
        if s[0] == t[0]:
            return f[0] + m
        c = t[0]
        l, r = left[0][c], right[0][c]
        return min(f[l] + n - l, f[r] + r) + m

Explain

该题解采用动态规划方法，结合了左右环形搜索策略，以找到拼写关键词所需的最少步数。解题的核心在于维护两个方向上字符的最近出现位置。对于环形字符串s中的每个字符，我们都计算它在顺时针和逆时针方向上到达关键词key中每个字符的最短路径。解决方案中使用了两个动态规划数组left和right，分别记录从当前位置i出发，向左和向右达到关键词key中每个字符的最近下标。动态规划过程从关键词key的最后一个字符向第一个字符逆序处理，对于每个字符，我们计算出从当前位置到下一个关键字符的最少步数，逐渐累加以达到全局最优解。

时间复杂度: O(m * n)

空间复杂度: O(n * 26 + n)

# https://space.bilibili.com/206214
class Solution:
    def findRotateSteps(self, s: str, t: str) -> int:
        # Convert characters to indices for easier manipulation
        s = [ord(c) - ord('a') for c in s]
        t = [ord(c) - ord('a') for c in t]
        n, m = len(s), len(t)

        # Position arrays for left and right character locations
        pos = [0] * 26  # Arbitrary initial values
        # Determine the last occurrence of each character
        for i, c in enumerate(s):
            pos[c] = i
        left = [None] * n  # Closest index to the left for each character
        for i, c in enumerate(s):
            left[i] = pos[:]
            pos[c] = i  # Update last position

        pos = [0] * 26  # Reset for right side computation
        for i in range(n - 1, -1, -1):
            pos[s[i]] = i
        right = [None] * n  # Closest index to the right for each character
        for i in range(n - 1, -1, -1):
            right[i] = pos[:]
            pos[s[i]] = i  # Update position

        # Record positions of each character in s
        pos = [[] for _ in range(26)]
        for i, b in enumerate(s):
            pos[b].append(i)

        f = [0] * n  # DP array to store minimal steps to current position
        for j in range(m - 1, 0, -1):
            c = t[j]
            if c == t[j - 1]:
                continue  # Skip if the character does not change
            nf = [0] * n  # New DP array for current character
            for i in pos[t[j - 1]]:  # Traverse through all positions of the previous character
                l, r = left[i][c], right[i][c]  # Left and right nearest positions
                res1 = f[l] + (n - l + i if l > i else i - l)  # Calculate steps
                res2 = f[r] + (n - i + r if r < i else r - i)
                if res2 < res1 : res1 = res2
                nf[i] = res1          # Store the minimal steps
            f = nf  # Move to the next character
        if s[0] == t[0]:
            return f[0] + m  # If first character matches, return steps
        c = t[0]
        l, r = left[0][c], right[0][c]
        return min(f[l] + n - l, f[r] + r) + m  # Return the minimal steps required

Explore

在动态规划的实现中，当遇到key中连续出现相同字符的情况时，通常可以跳过这些连续的重复字符的处理。因为在环形字符串中，从一个字符移动到它自身是不需要任何步骤的。所以算法在遍历到下一个字符时，如果这个字符与前一个字符相同，则可以直接继续使用之前计算的结果，而无需重新计算。这样做不但减少了不必要的计算，还可以保持状态数组的正确更新，从而优化整体的执行效率。

为了确保计算的正确性，算法在每个步骤中都计算了顺时针和逆时针两个方向的移动步数。对于每个关键字字符，算法维护了两个数组left和right，分别记录从当前位置向左（逆时针）和向右（顺时针）到达下一个关键字符的最近位置。通过比较从当前位置出发，向左和向右到达目标字符的步数，选择其中较小的一个作为最少步数。这种方法考虑了环形结构中的所有可能路径，确保了在任何情况下都能找到最优解。

这段逻辑实际上是简化了特定情况的处理，即当ring的首字符与key的首字符一致时，可以直接利用这一匹配点作为起始点。然而，这种处理确实没有考虑到所有边界情况，特别是当ring和key的长度不一致时。正确的做法应该是考虑从ring中任意一个与key首字符相匹配的位置开始的最优解。因此，还需要在所有可能的起始位置上计算完成整个key所需的最小步数，并从中选择最小的一个。这样可以确保考虑到所有的边界情况，并找到全局的最优解。

是的，该动态规划解法的效率在很大程度上依赖于key的长度。因为算法需要为key中的每个字符计算从当前位置到下一个字符的最少步数，这涉及到对环形字符串中的多个位置进行多次遍历和计算。当key的长度非常大时，这种方法的性能可能会受到影响，因为算法的时间复杂度与key的长度成线性关系。在实际应用中，如果key特别长，可能需要考虑优化算法，比如通过减少重复计算，使用更有效的数据结构来存储中间结果等方法来提高效率。