電子游戲“輻射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。
代碼
class Solution {public int findRotateSteps(String ring, String key) {int n=key.length(),m=ring.length();int[][] dp=new int[n][m];List<Integer> [] temp=new ArrayList[26];for(int i=0;i<26;i++)temp[i]=new ArrayList<>();for(int i=0;i<m;i++){temp[ring.charAt(i)-'a'].add(i);}//記錄相同字母在ring中出現的位置for (int i=0;i<n;i++)Arrays.fill(dp[i],0x3f3f3f);for(int c:temp[key.charAt(0)-'a'])dp[0][c]=Math.min(c,m-c)+1;//初始化第一步可能的移動for(int i=1;i<n;i++)for(int j:temp[key.charAt(i)-'a'])//遍歷這一步可能到達的位置for(int k:temp[key.charAt(i-1)-'a'])//遍歷上一步所有可能停留的位置dp[i][j]= Math.min(dp[i][j],Math.min(Math.abs(j-k), m-Math.abs(j-k))+1+dp[i-1][k]);int min=Integer.MAX_VALUE;for(int i=0;i<m;i++)min=Math.min(min,dp[n-1][i]);return min;}
}
