514、自由之路
视频游戏“辐射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 旋转拼出。
题解
1、记忆化搜索
class Solution {
public int findRotateSteps(String ring, String key) {
// ring字符串预处理
// 邻接表
List<Integer>[] rs = new List[26];
for (int i = 0;i < 26;i++) {
rs[i] = new ArrayList<>();
}
int k = 0;
for (char ch : ring.toCharArray()) {
rs[ch - 'a'].add(k);
k++;
}
// key处理
char[] keys = key.toCharArray();
// 状态数组，缓存中间值
int[][] dp = new int[ring.length()+1][key.length() + 1];
for (int i = 0;i < dp.length;i++) {
Arrays.fill(dp[i],-1);
}
return findRotateStepsCore(0,0,keys,rs,dp,ring.length());
}
private final static int MAX = Integer.MAX_VALUE>>1;
private int findRotateStepsCore(int r_idx,int k_idx,char[] keys,List<Integer>[] rs,int[][] dp,final int rlen) {
if (k_idx == keys.length) return 0;
if (dp[r_idx][k_idx] != -1) return dp[r_idx][k_idx];
int res = MAX;
for (int i:rs[keys[k_idx] - 'a']) {
int tmp = 1+Math.min(Math.abs(r_idx - i),Math.min(Math.abs(i+rlen-r_idx),Math.abs(r_idx+rlen - i)));
tmp += findRotateStepsCore(i,k_idx+1,keys,rs,dp,rlen);
res = Math.min(res,tmp);
}
return dp[r_idx][k_idx] = res;
}
}
// 记忆化搜索
class Solution {
public int findRotateSteps(String ring, String key) {
if (ring.isEmpty() || key.isEmpty()) {
return 0;
}
int n = ring.length(), m = key.length();
Map<Integer, List<Integer>> charIndexesMap = new HashMap<>();
int[][] memo = new int[n][m];
for (int i = 0; i < n; i++) {
int ch = ring.charAt(i);
if (charIndexesMap.containsKey(ch)) {
charIndexesMap.get(ch).add(i);
} else {
List<Integer> list = new ArrayList<>();
list.add(i);
charIndexesMap.put(ch, list);
}
}
return helper(charIndexesMap, memo, ring, key, 0, 0);
}
private int helper(Map<Integer, List<Integer>> charIndexesMap, int[][] memo, String ring, String key, int x, int y) {
if (y == key.length()) {
return 0;
}
if (memo[x][y] > 0) {
return memo[x][y];
}
int res = Integer.MAX_VALUE, n = ring.length();
for (int temp : charIndexesMap.get((int) key.charAt(y))) {
int diff = Math.abs(x - temp);
int step = Math.min(diff, n - diff);
res = Math.min(res, step + helper(charIndexesMap, memo, ring, key, temp, y + 1));
}
memo[x][y] = res + 1;
return memo[x][y];
}
}
动态规划
class Solution {
public int findRotateSteps(String ring, String key) {
char[] sring = ring.toCharArray();
char[] skey = key.toCharArray();
int[][] dp = new int[key.length()][ring.length()];
for(int i = 0 ; i < dp.length ; i ++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
int n = ring.length();
int count = Integer.MAX_VALUE;
for(int i = 0 ; i < skey.length ; i ++) {
for(int j = 0 ; j < n; j ++){
if(skey[i] == sring[j]){
if(i == 0)
dp[i][j] = Math.min(j, n - j);
else{
for(int k = 0 ; k < n ; k ++){
if(dp[i - 1][k] != Integer.MAX_VALUE){
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)));
}
}
}
if(i == skey.length - 1)
count = Math.min(count, dp[i][j]);
}
}
}
return count + skey.length;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
