# JAVA DP with explanation

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

• Great solution!

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