自由之路(困难题)

2020-11-14

电子游戏“辐射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 的下一个字符（下一阶段）, 直至完成所有拼写。
示例：

  
输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。
提示：

ring 和 key 的字符串长度取值范围均为 1 至 100；
两个字符串中都只有小写字符，并且均可能存在重复字符；
字符串 key 一定可以由字符串 ring 旋转拼出。
通过次数16,111提交次数32,458

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/freedom-trail
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

写了半天，只跑过了30+用例，修改后超时，看看官方题解

官方题解为了避免超时，为每个可能的字母设置了一个队列，每个队列保存那个字母的所有的下标（用来计算转动的步长）

dp表格是[key.length()][ring.length()]的二维数组，第一维代表key的第几个字符，第二维代表ring中的第几个字符
dp表格的值代表当前计算的最小的和。


class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length(), m = key.length();
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; ++i) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n; ++i) {
            pos[ring.charAt(i) - 'a'].add(i);//字母每出现一次向对应的队列加入对应的下标
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(dp[i], 0x3f3f3f);//初始化为正无穷
        }
        for (int i : pos[key.charAt(0) - 'a']) {//对于第一个字符（dp表格的第一行），初始化dp数组
            dp[0][i] = Math.min(i, n - i) + 1;
        }
        //思路是除了第一行之外，每一行的值都与上一行的第k-1个字符所对应的位置和上一行位置时的和有关
        for (int i = 1; i < m; ++i) {
            for (int j : pos[key.charAt(i) - 'a']) {
                for (int k : pos[key.charAt(i - 1) - 'a']) {
                    //第i行的内容是由第i-1行的内容计算而来的
                    //dp[i][j]是原有的值
                    //dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1是根据上一行计算出来的值，如果当前计算的值小于原先已有的值，替换掉。
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();//取得最后一行的最小值
    }
}

为了方便理解官方题解的dp过程，把自己写的递归思路写出来（超时了）


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

public class FreePath {

    public static void main(String[] args) {
        int sum = findRotateSteps("ababcab", "acbaacba");
        System.out.println(sum);
    }

    public static int findRotateSteps(String ring, String key) {
        char[] r = ring.toCharArray();
        char[] k = key.toCharArray();

        int[][] table = new int[key.length()][ring.length()];//dp表格
        for (int i = 0; i < key.length(); i++) {
            for (int j = 0; j < ring.length(); j++) {//初始化为最大值
                table[i][j] = Integer.MAX_VALUE;
            }
        }
        recursion(r, k, 0, 0, 0, table);//递归填写dp表

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < ring.length(); i++) {//查找dp表的最后一行，取最小值
            min = Math.min(table[key.length() - 1][i],min);
        }
        return min;
    }


    public static void recursion(char[] ring, char[] key, int point, int keyPoint, int sum, int[][] table) {
        if (point >= ring.length || keyPoint >= key.length) {//递归终止条件
            return;
        } else {
            int curSum = 0;
            for (int i = 0; i < ring.length; i++) {
                if (ring[i] == key[keyPoint]) {

                    //与上面的官方题解对应
                    //----------------------------------------------------------------------------------------
                    //第i行的内容是由第i-1行的内容计算而来的
                    //dp[i][j]是原有的值
                    //dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1是根据上一行计算出来的值，如果当前计算的值小于原先已有的值，替换掉。
                    //----------------------------------------------------------------------------------------
                    curSum = Math.min(Math.abs(i - point), ring.length - Math.abs(i - point)) + 1 + sum;//计算当前的总和
                    table[keyPoint][i] = Math.min(curSum, table[keyPoint][i]);//修改dp表
                    recursion(ring, key, i, keyPoint + 1, curSum, table);
                }
            }
        }
    }

}

官方题解