DP solution based on JAVA!


  • 0
    T
    class Solution {
        public int findRotateSteps(String ring, String key) {
            Map<Character,List<Integer>> map = new HashMap<>();
            char[] arrayRing = ring.toCharArray();
            for(int i=0;i<arrayRing.length;i++){
                char c = arrayRing[i];
                if(map.containsKey(c)==false){
                    map.put(c,new ArrayList<>());
                }
                map.get(c).add(i);
            }
            Integer[][] dp = new Integer[key.length()][ring.length()];
            DPsearch(map,dp,key.toCharArray(),ring.toCharArray(),0,0);
            return dp[0][0];
        }
        
        public int DPsearch(Map<Character,List<Integer>> map,Integer[][] dp,char[] arrayKey,char[] arrayRing,int keyIndex,int ringIndex){
            if(keyIndex==arrayKey.length){
                return 0;
            }
            
           if(dp[keyIndex][ringIndex]!=null){
                return dp[keyIndex][ringIndex];
            }
            
            List<Integer> list = map.get(arrayKey[keyIndex]);
            int min = Integer.MAX_VALUE;
            for(int index:list){
                int steps = 0;
                if(index<ringIndex){
                    steps = Math.min(ringIndex-index,Math.abs(index-ringIndex+arrayRing.length));
                }else{
                    steps = Math.min(index-ringIndex,Math.abs(ringIndex+arrayRing.length-index));
                }
                
                int nextsteps = DPsearch(map,dp,arrayKey,arrayRing,keyIndex+1,index); 
                min = Math.min(min,steps+1+nextsteps);
                
            }
            
            dp[keyIndex][ringIndex] = min;
            return dp[keyIndex][ringIndex];
            
        }
    }
    

Log in to reply
 

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