# 39 ms Java Solution

• ``````public class Solution {

int dfs(List<Integer> [] c, int m, char[] s, int x, int y, int[][] dp) {
if (x == s.length) {
return 0;
}
if (dp[x][y] < Integer.MAX_VALUE) {
return dp[x][y];
}
for (int k : c[s[x] - 'a']) {
int diff = Math.abs(y - k);
dp[x][y] = Math.min(dp[x][y], dfs(c, m, s, x + 1, k, dp) + Math.min(diff, m - diff));
}
return dp[x][y];
}

public int findRotateSteps(String ring, String key) {
int m = ring.length();
int n = key.length();
int [][] dp = new int[n][m];

List<Integer> [] c = new List[26];
for (int i = 0; i < 26; i++) {
c[i] = new ArrayList<Integer>();
}

for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
dp[i][j] = Integer.MAX_VALUE;
}
}

return dfs(c, m, key.toCharArray(), 0, 0, dp) + n;
}
}
``````

• or use HashMap

``````public class Solution {

int dfs(HashMap<Character, List<Integer>> map, int m, char[] s, int x, int y, int[][] dp) {
if (x == s.length) {
return 0;
}
if (dp[x][y] > 0) {
return dp[x][y];
}
dp[x][y] = Integer.MAX_VALUE;
List<Integer> list = map.get(s[x]);
for (int k : list) {
int diff = Math.abs(y - k);
dp[x][y] = Math.min(dp[x][y], dfs(map, m, s, x + 1, k, dp) + Math.min(diff, m - diff) + 1);
}
return dp[x][y];
}

public int findRotateSteps(String ring, String key) {
int m = ring.length();
int n = key.length();
int [][] dp = new int[n][m];

HashMap<Character, List<Integer>> map = new HashMap<>();
for (int j = 0; j < m; j++) {
char c = ring.charAt(j);
if (!map.containsKey(c)) {
map.put(c, new ArrayList<Integer>());
}