514. 自由之路 - 力扣（LeetCode）

一、题目

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

二、代码

class Solution {
    public int findRotateSteps(String ring, String key) {
        // String转化为字符串数组
        char[] ringC = ring.toCharArray();
        char[] keyC = key.toCharArray();

        // 构造表盘上每一个字符都有哪些位置，存储在Map中
        HashMap<Character, ArrayList<Integer>> ringMap = new HashMap<>();
        for (int i = 0; i < ringC.length; i++) {
            if (ringMap.containsKey(ringC[i])) {
                ringMap.get(ringC[i]).add(i);
            } else {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(i);
                ringMap.put(ringC[i], arr);
            }
        }

        // 创建缓存数组
        int[][] dp = new int[keyC.length][ringC.length];

        return process(0, keyC, ringMap, 0, ringC.length, dp);

    }

    // 当前检查要拨打的index位置的字符的最小步数，此时电话机上的指针指向圆盘的ringIndex位置
    public int process(int index, char[] keyC, HashMap<Character, ArrayList<Integer>> ringMap, int ringIndex, int ringLen, int[][] dp) {
        // 当遍历完所有的要拨打的字符，当前来到越界位置，返回0步数
        if (index == keyC.length) {
            return 0;
        }

        // 如果缓存中已经有结果了，直接返回
        if (dp[index][ringIndex] != 0) {
            return dp[index][ringIndex];
        }

        // 找到当前要拨打的keyC[index]字符在电话机的圆盘上的全部位置，递归尝试每一个位置，去找到步数最小的转轮方法
        int min = Integer.MAX_VALUE;
        // 获取圆盘上所有keyC[index]字符的位置
        ArrayList<Integer> nextPositions = ringMap.get(keyC[index]);
        // 尝试每一个转盘上的位置
        for (Integer i : nextPositions) {
            // 尝试顺时针转到i位置和逆时针转到i位置(minPay(ringIndex, i, ringLen))，找到最小消耗，并且再加上后续的最小步数(process(index + 1, keyC, ringMap, i, ringLen, dp))，就是我们要求的当前层的结果
            min = Math.min(min, minPay(ringIndex, i, ringLen) + process(index + 1, keyC, ringMap, i, ringLen, dp));
        }
        
        // 存入缓存  这里要+1，因为每转到一个字符，还需要点一下按钮，这也算是一次步数
        dp[index][ringIndex] = min + 1;
        return dp[index][ringIndex];
    }

    // 将指针从fromIndex位置转到toIndex位置的最小步数
    // 这里会尝试顺时针转到toIndex和逆时针转到toIndex，看哪种转法步数最少
    public int minPay(int fromIndex, int toIndex, int ringLen) {
        // Math.abs(toIndex - fromIndex)   顺时针
        // Math.abs(ringLen - Math.max(toIndex, fromIndex) + Math.min(fromIndex, toIndex)) 逆时针   这个就是个简单的数学关系，很好理解，就是注意把fromIndex < toIndex和fromIndex >= toIndex两种情况都考虑进去即可
        return Math.min(Math.abs(toIndex - fromIndex), Math.abs(ringLen - Math.max(toIndex, fromIndex) + Math.min(fromIndex, toIndex)));
    }



    // 这道题没有必要改动态规划，因为这道题的枚举过程无法进行斜率优化，枚举过程中的相对位置关系不是固定的，依赖的位置数量也是不固定的。
}

三、解题思路 

去尝试每一个位置的最小步数的转法，然后从所有结果中找到最小值即可。