# Java Recursive + Memo

• 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
``````

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;
}

``````

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