電子游戲 “輻射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 旋轉拼出，
解題思路
class Solution {
List<Integer>[] pos = new List[26];
int[][] dp;
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();
for(int i = 0; i < 26; i++) {
pos[i] = new ArrayList<>();
}
for(int i = 0; i < n; i++) {
pos[ring.charAt(i) - 'a'].add(i);
}
dp = new int[n][m];
for(int i = 0; i < n; i++) {
Arrays.fill(dp[i], -1);
}
return dfs(n, 0, key, 0);
}
public int dfs(int n, int now, String key, int index) {
if(index == key.length()) {
return 0;
}
if(dp[now][index] > 0) {
return dp[now][index];
}
List<Integer> list = pos[key.charAt(index) - 'a'];
int min = 0xfffff;
for (Integer one : list) {
int dis = 1 + Math.min(Math.abs(now - one), n - Math.abs(now - one)) + dfs(n, one, key, index + 1);
if(dis < min) {
min = dis;
}
}
dp[now][index] = min;
return min;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/213766.html
標籤：其他