Java Recursive + Memo


  • 0
    D

    The goal of the problem is to grab all the possible solutions, and finding the minimum.

    First we start by recursively going through each iteration of decisions. Every recursive call will bring us to a solution as long as our ring includes every character in our key.

    We need to calculate the shortest amount of moves from one point to another in a ring. Which is simply:

    moveCost = Math.min(Math.abs(ringIndex - currentRingIndex), (ring.length() - Math.max(ringIndex, currentRingIndex)) + Math.min(ringIndex, currentRingIndex)) + 1 //Button press cost is 1
    

    alt text

    We will then need to find the minimum cost for every possible solution, as seen in code below. Read comments:

    
    
        public int findRotateSteps(String ring, String key) {
            int[][] memo = new int[ring.length()][key.length()];
            for (int[] ints : memo) {
                Arrays.fill(ints, -1);
            }
            return findRotateSteps(memo, 0, ring, key);
        }
    
        public int findRotateSteps(int[][] memo, int currentRingIndex, String ring, String key) {
            if (key.length() == 0){
                return 0;
            }
    
            int retVal = memo[currentRingIndex][key.length() - 1]; //Grab precomputed value from memo
            if (retVal != -1){
                return retVal;
            }
    
            final char currentChar = key.charAt(0);
    
            int minMoves = Integer.MAX_VALUE;
            for (int ringIndex = 0; ringIndex < ring.length(); ringIndex++) {
                if (currentChar != ring.charAt(ringIndex)){     //Do we need to move to this character?
                    continue;                                   //no
                }
    
                int moveCost = Math.min(        //Get the minimum cost to move, both clockwise and counter clockwise
                        Math.abs(ringIndex - currentRingIndex),
                        (ring.length() - Math.max(ringIndex, currentRingIndex)) + Math.min(ringIndex, currentRingIndex))
                        + BUTTON_PRESS_COST;    //Add cost to press button
    
    
                int remainingMoveCost = findRotateSteps(memo, ringIndex, ring, key.substring(1)); //Recursive call for remaining steps
    
                int totalCost = moveCost + remainingMoveCost;
    
                minMoves = Math.min(minMoves, totalCost);   //There are multiple solutions. Save the minimum step solution.
            }
    
            memo[currentRingIndex][key.length() - 1] = minMoves; //Cache value to prevent future computations.
    
            return minMoves;
        }
    
    

Log in to reply
 

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