share my java solution!


  • 0
    T
    public class Solution {
        public int findRotateSteps(String ring, String key) {
            Map<Character,List<Integer>> map = new HashMap<>();
            for(int i=0;i<ring.length();i++){
                char c=ring.charAt(i);
                if(map.containsKey(c)==false){
                    map.put(c,new ArrayList<>());
                }
                map.get(c).add(i);
            }
            
            int[][] dp = new int[key.length()][ring.length()];
            char target = key.charAt(0);
            List<Integer> pre_list = map.get(target);
            
            for(int index:pre_list){
                dp[0][index]=Math.min(index,ring.length()-index);
            }
            
            
            for(int i=1;i<key.length();i++){
                  target = key.charAt(i);
                  Arrays.fill(dp[i],Integer.MAX_VALUE);
                  List<Integer> cur_list = map.get(target);
                
                  for(int index:cur_list){
                        for(int pre_index:pre_list){
                            int step=Math.min(Math.abs(index-pre_index),ring.length()-Math.abs(index-pre_index));
                            dp[i][index]=Math.min(step+dp[i-1][pre_index],dp[i][index]);
                        }
                  }
                 pre_list=cur_list;
            }
            
            int min=Integer.MAX_VALUE;
            for(int i=0;i<dp[key.length()-1].length;i++){
                min=Math.min(dp[key.length()-1][i],min);
            }
            return min+key.length();
            
        }
    }
    

Log in to reply
 

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