39 ms Java Solution


  • 0
    I
    public class Solution {
        
        int dfs(List<Integer> [] c, int m, char[] s, int x, int y, int[][] dp) {
            if (x == s.length) {
                return 0;
            }
            if (dp[x][y] < Integer.MAX_VALUE) {
                return dp[x][y];
            }
            for (int k : c[s[x] - 'a']) {
                int diff = Math.abs(y - k);
                dp[x][y] = Math.min(dp[x][y], dfs(c, m, s, x + 1, k, dp) + Math.min(diff, m - diff));
            }
            return dp[x][y];
        }
    
        public int findRotateSteps(String ring, String key) {
            int m = ring.length();
            int n = key.length();
            int [][] dp = new int[n][m];
            
            List<Integer> [] c = new List[26];
            for (int i = 0; i < 26; i++) {
                c[i] = new ArrayList<Integer>();
            }
            
            for (int j = 0; j < m; j++) {
                c[ring.charAt(j) - 'a'].add(j);
                for (int i = 0; i < n; i++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
            
            return dfs(c, m, key.toCharArray(), 0, 0, dp) + n;
        }
    }
    

  • 0
    I

    or use HashMap

    public class Solution {
        
        int dfs(HashMap<Character, List<Integer>> map, int m, char[] s, int x, int y, int[][] dp) {
            if (x == s.length) {
                return 0;
            }
            if (dp[x][y] > 0) {
                return dp[x][y];
            }
            dp[x][y] = Integer.MAX_VALUE;
            List<Integer> list = map.get(s[x]);
            for (int k : list) {
                int diff = Math.abs(y - k);
                dp[x][y] = Math.min(dp[x][y], dfs(map, m, s, x + 1, k, dp) + Math.min(diff, m - diff) + 1);
            }
            return dp[x][y];
        }
    
        public int findRotateSteps(String ring, String key) {
            int m = ring.length();
            int n = key.length();
            int [][] dp = new int[n][m];
            
            HashMap<Character, List<Integer>> map = new HashMap<>();
            for (int j = 0; j < m; j++) {
                char c = ring.charAt(j);
                if (!map.containsKey(c)) {
                    map.put(c, new ArrayList<Integer>());
                }            
                map.get(c).add(j);
            }
            
            return dfs(map, m, key.toCharArray(), 0, 0, dp);
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.