这道题是LeetCode 514 - 自由之路一个动态规划问题。我来提供解决方案和详细解释。解题思路这个问题可以看作是在环形字符串中寻找最优路径使得拼出目标字符串的步数最少。关键点环形结构指针可以顺时针或逆时针转动状态定义dp[i][j] 表示拼出key的前i个字符且指针指向ring的第j个字符时的最小步数状态转移对于每个字符考虑从之前的位置移动到当前位置的最短距离代码实现classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 记录每个字符在ring中的所有位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}// dp[i][j] 表示拼出key的前i个字符且指针指向ring的第j个位置时的最小步数int[][]dpnewint[m][n];for(inti0;im;i){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 初始化第一个字符charfirstCharkey.charAt(0);for(intpos:positions[firstChar-a]){// 从0位置转到pos的最小距离intdistMath.min(pos,n-pos);dp[0][pos]dist1;// 1 是按按钮的步骤}// 处理剩余的字符for(inti1;im;i){charcurrCharkey.charAt(i);charprevCharkey.charAt(i-1);for(intcurrPos:positions[currChar-a]){for(intprevPos:positions[prevChar-a]){if(dp[i-1][prevPos]!Integer.MAX_VALUE){// 计算从prevPos到currPos的最小距离intdistgetMinDistance(ring.length(),prevPos,currPos);dp[i][currPos]Math.min(dp[i][currPos],dp[i-1][prevPos]dist1);}}}}// 找出拼出整个key的最小步数intresultInteger.MAX_VALUE;for(intpos:positions[key.charAt(m-1)-a]){resultMath.min(result,dp[m-1][pos]);}returnresult;}// 计算在环形中从i到j的最短距离privateintgetMinDistance(intn,inti,intj){intforwardMath.abs(j-i);intbackwardn-forward;returnMath.min(forward,backward);}}优化版本使用记忆化搜索classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 记录每个字符在ring中的所有位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}// 记忆化数组memo[i][j] 表示已经匹配了key的前i个字符当前在ring的第j个位置int[][]memonewint[m][n];for(inti0;im;i){Arrays.fill(memo[i],-1);}returndfs(ring,key,0,0,positions,memo);}privateintdfs(Stringring,Stringkey,intkeyIndex,intringIndex,ListInteger[]positions,int[][]memo){// 如果已经拼完所有字符if(keyIndexkey.length()){return0;}// 如果已经计算过if(memo[keyIndex][ringIndex]!-1){returnmemo[keyIndex][ringIndex];}chartargetkey.charAt(keyIndex);intnring.length();intminStepsInteger.MAX_VALUE;// 尝试所有可能的目标位置for(intnextPos:positions[target-a]){// 计算从当前位置到目标位置的最小旋转距离intdistgetMinDistance(n,ringIndex,nextPos);// 递归计算剩余字符intstepsdfs(ring,key,keyIndex1,nextPos,positions,memo);// 总步数 旋转距离 按按钮(1) 剩余步数minStepsMath.min(minSteps,dist1steps);}memo[keyIndex][ringIndex]minSteps;returnminSteps;}privateintgetMinDistance(intn,inti,intj){intforwardMath.abs(j-i);intbackwardn-forward;returnMath.min(forward,backward);}}详细示例假设ring godding, key gd执行过程初始指针在位置0字符’g’拼出第一个字符’g’位置0已经有’g’不需要旋转步数0 1 1拼出第二个字符’d’d’在位置2和3从位置0到位置2顺时针2步逆时针5步 → 最小2步从位置0到位置3顺时针3步逆时针4步 → 最小3步选择位置2总步数 1 2 1 4最终结果4复杂度分析时间复杂度O(m * n²)m是key的长度n是ring的长度每个状态需要遍历所有可能的位置空间复杂度O(m * n)需要存储dp数组或memo数组优化思路预处理距离可以预先计算任意两个位置之间的最短距离使用BFS将问题转化为图的最短路径问题双向BFS从key的两端同时进行搜索// 预处理距离的优化版本classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 预处理任意两点之间的最短距离int[][]distnewint[n][n];for(inti0;in;i){for(intj0;jn;j){intforwardMath.abs(j-i);intbackwardn-forward;dist[i][j]Math.min(forward,backward);}}// 记录每个字符的位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}int[][]dpnewint[m][n];for(inti0;im;i){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 初始化第一个字符charfirstCharkey.charAt(0);for(intpos:positions[firstChar-a]){dp[0][pos]dist[0][pos]1;}// 动态规划for(inti1;im;i){charcurrCharkey.charAt(i);for(intcurrPos:positions[currChar-a]){charprevCharkey.charAt(i-1);for(intprevPos:positions[prevChar-a]){if(dp[i-1][prevPos]!Integer.MAX_VALUE){dp[i][currPos]Math.min(dp[i][currPos],dp[i-1][prevPos]dist[prevPos][currPos]1);}}}}intresultInteger.MAX_VALUE;for(intpos:positions[key.charAt(m-1)-a]){resultMath.min(result,dp[m-1][pos]);}returnresult;}}这个解法通过动态规划或记忆化搜索有效地解决了环形字符串中的最优路径问题。
DeepSeek LeetCode 514. 自由之路 public int findRotateSteps(String ring, String key) 一个动态规划问题
这道题是LeetCode 514 - 自由之路一个动态规划问题。我来提供解决方案和详细解释。解题思路这个问题可以看作是在环形字符串中寻找最优路径使得拼出目标字符串的步数最少。关键点环形结构指针可以顺时针或逆时针转动状态定义dp[i][j] 表示拼出key的前i个字符且指针指向ring的第j个字符时的最小步数状态转移对于每个字符考虑从之前的位置移动到当前位置的最短距离代码实现classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 记录每个字符在ring中的所有位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}// dp[i][j] 表示拼出key的前i个字符且指针指向ring的第j个位置时的最小步数int[][]dpnewint[m][n];for(inti0;im;i){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 初始化第一个字符charfirstCharkey.charAt(0);for(intpos:positions[firstChar-a]){// 从0位置转到pos的最小距离intdistMath.min(pos,n-pos);dp[0][pos]dist1;// 1 是按按钮的步骤}// 处理剩余的字符for(inti1;im;i){charcurrCharkey.charAt(i);charprevCharkey.charAt(i-1);for(intcurrPos:positions[currChar-a]){for(intprevPos:positions[prevChar-a]){if(dp[i-1][prevPos]!Integer.MAX_VALUE){// 计算从prevPos到currPos的最小距离intdistgetMinDistance(ring.length(),prevPos,currPos);dp[i][currPos]Math.min(dp[i][currPos],dp[i-1][prevPos]dist1);}}}}// 找出拼出整个key的最小步数intresultInteger.MAX_VALUE;for(intpos:positions[key.charAt(m-1)-a]){resultMath.min(result,dp[m-1][pos]);}returnresult;}// 计算在环形中从i到j的最短距离privateintgetMinDistance(intn,inti,intj){intforwardMath.abs(j-i);intbackwardn-forward;returnMath.min(forward,backward);}}优化版本使用记忆化搜索classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 记录每个字符在ring中的所有位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}// 记忆化数组memo[i][j] 表示已经匹配了key的前i个字符当前在ring的第j个位置int[][]memonewint[m][n];for(inti0;im;i){Arrays.fill(memo[i],-1);}returndfs(ring,key,0,0,positions,memo);}privateintdfs(Stringring,Stringkey,intkeyIndex,intringIndex,ListInteger[]positions,int[][]memo){// 如果已经拼完所有字符if(keyIndexkey.length()){return0;}// 如果已经计算过if(memo[keyIndex][ringIndex]!-1){returnmemo[keyIndex][ringIndex];}chartargetkey.charAt(keyIndex);intnring.length();intminStepsInteger.MAX_VALUE;// 尝试所有可能的目标位置for(intnextPos:positions[target-a]){// 计算从当前位置到目标位置的最小旋转距离intdistgetMinDistance(n,ringIndex,nextPos);// 递归计算剩余字符intstepsdfs(ring,key,keyIndex1,nextPos,positions,memo);// 总步数 旋转距离 按按钮(1) 剩余步数minStepsMath.min(minSteps,dist1steps);}memo[keyIndex][ringIndex]minSteps;returnminSteps;}privateintgetMinDistance(intn,inti,intj){intforwardMath.abs(j-i);intbackwardn-forward;returnMath.min(forward,backward);}}详细示例假设ring godding, key gd执行过程初始指针在位置0字符’g’拼出第一个字符’g’位置0已经有’g’不需要旋转步数0 1 1拼出第二个字符’d’d’在位置2和3从位置0到位置2顺时针2步逆时针5步 → 最小2步从位置0到位置3顺时针3步逆时针4步 → 最小3步选择位置2总步数 1 2 1 4最终结果4复杂度分析时间复杂度O(m * n²)m是key的长度n是ring的长度每个状态需要遍历所有可能的位置空间复杂度O(m * n)需要存储dp数组或memo数组优化思路预处理距离可以预先计算任意两个位置之间的最短距离使用BFS将问题转化为图的最短路径问题双向BFS从key的两端同时进行搜索// 预处理距离的优化版本classSolution{publicintfindRotateSteps(Stringring,Stringkey){intnring.length();intmkey.length();// 预处理任意两点之间的最短距离int[][]distnewint[n][n];for(inti0;in;i){for(intj0;jn;j){intforwardMath.abs(j-i);intbackwardn-forward;dist[i][j]Math.min(forward,backward);}}// 记录每个字符的位置ListInteger[]positionsnewArrayList[26];for(inti0;i26;i){positions[i]newArrayList();}for(inti0;in;i){positions[ring.charAt(i)-a].add(i);}int[][]dpnewint[m][n];for(inti0;im;i){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 初始化第一个字符charfirstCharkey.charAt(0);for(intpos:positions[firstChar-a]){dp[0][pos]dist[0][pos]1;}// 动态规划for(inti1;im;i){charcurrCharkey.charAt(i);for(intcurrPos:positions[currChar-a]){charprevCharkey.charAt(i-1);for(intprevPos:positions[prevChar-a]){if(dp[i-1][prevPos]!Integer.MAX_VALUE){dp[i][currPos]Math.min(dp[i][currPos],dp[i-1][prevPos]dist[prevPos][currPos]1);}}}}intresultInteger.MAX_VALUE;for(intpos:positions[key.charAt(m-1)-a]){resultMath.min(result,dp[m-1][pos]);}returnresult;}}这个解法通过动态规划或记忆化搜索有效地解决了环形字符串中的最优路径问题。
