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 的下一个字符（下一阶段）, 直至完成所有拼写。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/freedom-trail
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、暴力递归
首先我们要引入一个函数minDial()
这个函数解决环内i1下标与i2下标顺时针或逆时针的最短距离
//n为转盘的长度
public int minDial(int i,int j,int n){
return Math.min(Math.abs(i-j),Math.min(i,j)+n-Math.max(i,j));
}process(0, 0, aim, map, N)
递归含义:从上一个拨号位置,到下一个要拨号的字母,最小的代价是什么
我们需要用一个哈希表记录每个字母出现的位置
在递归中,遍历下一个字母每个位置,取最小的代价
public static int findRotateSteps(String r, String k) {
char[] ring = r.toCharArray();
int N = ring.length;
HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < N; i++) {
if (!map.containsKey(ring[i])) {
map.put(ring[i], new ArrayList<>());
}
map.get(ring[i]).add(i);
}
char[] str = k.toCharArray();
int M = str.length;
return process(0, 0, str, map, N);
}
// 电话里：指针指着的上一个按键preButton
// 目标里：此时要搞定哪个字符？keyIndex
// map : key 一种字符 value: 哪些位置拥有这个字符
// N: 电话大小
// f(0, 0, aim, map, N)
public static int process(int preButton, int index, char[] str, HashMap<Character, ArrayList<Integer>> map, int N,int[][] dp) {
if (index == str.length) {
return 0;
}
int ans = Integer.MAX_VALUE;
// 还有字符需要搞定
char cur = str[index];
ArrayList<Integer> nextPositions = map.get(cur);
for (int next : nextPositions) {
int cost = dial(preButton, next, N) + 1 + process(next, index + 1, str, map, N);
ans = Math.min(ans, cost);
}
return ans;
}
public static int dial(int i1, int i2, int size) {
return Math.min(Math.abs(i1 - i2), Math.min(i1, i2) + size - Math.max(i1, i2));
}
二、记忆化搜索
我们使用dp来记录每个位置出现的答案,如果出现过,直接返回就行了,初始化全为-1,代表没有出现过
public int N;
public int findRotateSteps(String ring, String key) {
HashMap<Character,ArrayList<Integer>> map=new HashMap<>();
char[] r=ring.toCharArray();
N=r.length;
for(int i=0;i<N;i++){
if(!map.containsKey(r[i])){
map.put(r[i],new ArrayList<Integer>());
}
map.get(r[i]).add(i);
}
char[] aim=key.toCharArray();
int m=aim.length;
int[][] dp=new int[N][m+1];
for(int i=0;i<N;i++){
for(int j=0;j<=m;j++){
dp[i][j]=-1;
}
}
return process(0,0,aim,map,dp);
}
public int process(int pre,int index,char[] aim,HashMap<Character,ArrayList<Integer>> map,int[][] dp){
if(dp[pre][index]!=-1){
return dp[pre][index];
}
int ans=Integer.MAX_VALUE;
if(index==aim.length){
ans=0;
}else{
ArrayList<Integer> nextPosition=map.get(aim[index]);
for(int next:nextPosition){
ans=Math.min(ans,minDial(pre,next,N)+1+process(next,index+1,aim,map,dp));
}
}
dp[pre][index]=ans;
return ans;
}
public int minDial(int i,int j,int n){
return Math.min(Math.abs(i-j),Math.min(i,j)+n-Math.max(i,j));
}动态规划
我们直接根据暴力递归改动态规划
主函数调用递归的参数,我们返回dp0;
因为每次调用递归都是index+1,因此dp要反着填
我们从右往左填
dpi代表从i出发到aim[j]的最小代价
我们可以从下到上填好dpi
public int minDial(int i,int j,int n){
return Math.min(Math.abs(i-j),Math.min(i,j)+n-Math.max(i,j));
}
public int findRotateSteps(String ring, String key) {
HashMap<Character,ArrayList<Integer>> map=new HashMap<>();
char[] r=ring.toCharArray();
int n=r.length;
for(int i=0;i<n;i++){
if(!map.containsKey(r[i])){
map.put(r[i],new ArrayList<Integer>());
}
map.get(r[i]).add(i);
}
char[] aim=key.toCharArray();
int m=aim.length;
int[][] dp=new int[n+1][m+1];
for(int j=m-1;j>=0;j--){
for(int i=n-1;i>=0;i--){
char c=aim[j];
int res=Integer.MAX_VALUE;
for(int next:map.get(c)){
res=Math.min(res,dp[next][j+1]+1+minDial(i,next,n));
}
dp[i][j]=res;
}
}
return dp[0][0];
}
