这道题是LeetCode 514 - 自由之路，一个动态规划问题。我来提供解决方案和详细解释。

解题思路

这个问题可以看作是：在环形字符串中寻找最优路径，使得拼出目标字符串的步数最少。

关键点：

1. 环形结构：指针可以顺时针或逆时针转动
2. 状态定义：dp[i][j] 表示拼出key的前i个字符，且指针指向ring的第j个字符时的最小步数
3. 状态转移：对于每个字符，考虑从之前的位置移动到当前位置的最短距离

代码实现

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        
        // 记录每个字符在ring中的所有位置
        List<Integer>[] positions = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            positions[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            positions[ring.charAt(i) - 'a'].add(i);
        }
        
        // dp[i][j] 表示拼出key的前i个字符，且指针指向ring的第j个位置时的最小步数
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        // 初始化第一个字符
        char firstChar = key.charAt(0);
        for (int pos : positions[firstChar - 'a']) {
            // 从0位置转到pos的最小距离
            int dist = Math.min(pos, n - pos);
            dp[0][pos] = dist + 1; // +1 是按按钮的步骤
        }
        
        // 处理剩余的字符
        for (int i = 1; i < m; i++) {
            char currChar = key.charAt(i);
            char prevChar = key.charAt(i - 1);
            
            for (int currPos : positions[currChar - 'a']) {
                for (int prevPos : positions[prevChar - 'a']) {
                    if (dp[i-1][prevPos] != Integer.MAX_VALUE) {
                        // 计算从prevPos到currPos的最小距离
                        int dist = getMinDistance(ring.length(), prevPos, currPos);
                        dp[i][currPos] = Math.min(dp[i][currPos], 
                                                   dp[i-1][prevPos] + dist + 1);
                    }
                }
            }
        }
        
        // 找出拼出整个key的最小步数
        int result = Integer.MAX_VALUE;
        for (int pos : positions[key.charAt(m-1) - 'a']) {
            result = Math.min(result, dp[m-1][pos]);
        }
        
        return result;
    }
    
    // 计算在环形中从i到j的最短距离
    private int getMinDistance(int n, int i, int j) {
        int forward = Math.abs(j - i);
        int backward = n - forward;
        return Math.min(forward, backward);
    }
}

优化版本（使用记忆化搜索）

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        
        // 记录每个字符在ring中的所有位置
        List<Integer>[] positions = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            positions[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            positions[ring.charAt(i) - 'a'].add(i);
        }
        
        // 记忆化数组：memo[i][j] 表示已经匹配了key的前i个字符，当前在ring的第j个位置
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], -1);
        }
        
        return dfs(ring, key, 0, 0, positions, memo);
    }
    
    private int dfs(String ring, String key, int keyIndex, int ringIndex, 
                    List<Integer>[] positions, int[][] memo) {
        // 如果已经拼完所有字符
        if (keyIndex == key.length()) {
            return 0;
        }
        
        // 如果已经计算过
        if (memo[keyIndex][ringIndex] != -1) {
            return memo[keyIndex][ringIndex];
        }
        
        char target = key.charAt(keyIndex);
        int n = ring.length();
        int minSteps = Integer.MAX_VALUE;
        
        // 尝试所有可能的目标位置
        for (int nextPos : positions[target - 'a']) {
            // 计算从当前位置到目标位置的最小旋转距离
            int dist = getMinDistance(n, ringIndex, nextPos);
            
            // 递归计算剩余字符
            int steps = dfs(ring, key, keyIndex + 1, nextPos, positions, memo);
            
            // 总步数 = 旋转距离 + 按按钮(1) + 剩余步数
            minSteps = Math.min(minSteps, dist + 1 + steps);
        }
        
        memo[keyIndex][ringIndex] = minSteps;
        return minSteps;
    }
    
    private int getMinDistance(int n, int i, int j) {
        int forward = Math.abs(j - i);
        int backward = n - forward;
        return Math.min(forward, backward);
    }
}

详细示例

假设：

ring = "godding", key = "gd"

执行过程：

1. 初始指针在位置0（字符’g’）
2. 拼出第一个字符’g’：
   • 位置0已经有’g’，不需要旋转
   • 步数：0 + 1 = 1
3. 拼出第二个字符’d’：
   • 'd’在位置2和3
   • 从位置0到位置2：顺时针2步，逆时针5步 → 最小2步
   • 从位置0到位置3：顺时针3步，逆时针4步 → 最小3步
   • 选择位置2：总步数 = 1 + 2 + 1 = 4
4. 最终结果：4

复杂度分析

• 时间复杂度：O(m * n²)

  • m是key的长度，n是ring的长度
  • 每个状态需要遍历所有可能的位置

• 空间复杂度：O(m * n)

  • 需要存储dp数组或memo数组

优化思路

1. 预处理距离：可以预先计算任意两个位置之间的最短距离
2. 使用BFS：将问题转化为图的最短路径问题
3. 双向BFS：从key的两端同时进行搜索

// 预处理距离的优化版本
class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        
        // 预处理任意两点之间的最短距离
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int forward = Math.abs(j - i);
                int backward = n - forward;
                dist[i][j] = Math.min(forward, backward);
            }
        }
        
        // 记录每个字符的位置
        List<Integer>[] positions = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            positions[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            positions[ring.charAt(i) - 'a'].add(i);
        }
        
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        
        // 初始化第一个字符
        char firstChar = key.charAt(0);
        for (int pos : positions[firstChar - 'a']) {
            dp[0][pos] = dist[0][pos] + 1;
        }
        
        // 动态规划
        for (int i = 1; i < m; i++) {
            char currChar = key.charAt(i);
            for (int currPos : positions[currChar - 'a']) {
                char prevChar = key.charAt(i - 1);
                for (int prevPos : 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);
                    }
                }
            }
        }
        
        int result = Integer.MAX_VALUE;
        for (int pos : positions[key.charAt(m-1) - 'a']) {
            result = Math.min(result, dp[m-1][pos]);
        }
        
        return result;
    }
}

这个解法通过动态规划或记忆化搜索，有效地解决了环形字符串中的最优路径问题。