JAVA DP with explanation


  • 4

    The dp is a 2D integer array, with height = the length of ring, with width = the length of key. So DP[i][j] represents that if we want to spell the next character key[j], and at the same time the 12:00 aligns with the ring[i], then what is the minimum steps to spell the whole key start at key[j]. If we finish the DP array, then the answer is just DP[0][0], which means the minimum steps to spell the whole key start at key[0], if currently 12:00 aligns with the ring[0], and this is exactly the original problem. And don't forget to plus the length of key, which is the steps we need to push the button.

    // by fallcreek
    public class Solution {
        public int findRotateSteps(String ring, String key) {        
            int[][] dp = new int[ring.length()][key.length()];
            for(int[] line : dp)    Arrays.fill(line, -1);
            
            return helper(ring, 0, key, 0, dp) + key.length();
        }
        
        public int helper(String ring, int rIndex, String key, int kIndex, int[][] dp){
            if(kIndex == key.length()) return 0;
            if(dp[rIndex][kIndex] != -1) return dp[rIndex][kIndex];
            
            char dest = key.charAt(kIndex);
            
            int nextIndex = ring.indexOf(dest);
            int sol = Integer.MAX_VALUE;
            do{
                int move = Math.min(Math.abs(rIndex - nextIndex), ring.length() - Math.abs(rIndex - nextIndex));
                int remain = helper(ring, nextIndex, key, kIndex + 1, dp);
                sol = Math.min(sol, move + remain);
                nextIndex = ring.indexOf(dest, nextIndex + 1);
            }while(nextIndex != -1);
            dp[rIndex][kIndex] = sol;
            return sol;
        }
    }
    

  • 0

    Great solution!


Log in to reply
 

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