# Clear DFS + Memorization solution in Java

• A naive DFS solution will lead to TLE. So we need a better solution. In the naive DFS, there are many duplicate computations, so we can use a 2D array, let's say it is called dp, to store the answers we have already known. For the dp array, dp[i][j] represents the best solution we can have for starting at index j in string key, if we use the ith element from string ring. Here is the code below:

public class Solution {

``````public int findRotateSteps(String ring, String key) { // DFS solution
Map<Character, List<Integer>> map = new HashMap<>();
char[] chs = ring.toCharArray();
char[] ks = key.toCharArray();
for (int i = 0; i < chs.length; i++) {
if (!map.containsKey(chs[i])) map.put(chs[i], new ArrayList<Integer>());
}
int[][] dp = new int[ring.length()][key.length()];
return dfs(ks, chs.length, 0, map, 0, 0, dp);
}

private int dfs(char[] ks, int length, int index, Map<Character, List<Integer>> map, int steps, int cur, int[][] dp) {
if (index < ks.length && dp[cur][index] != 0) return steps + dp[cur][index];
if (index == ks.length) {
return steps;
}

List<Integer> next = map.get(ks[index]);
int min = Integer.MAX_VALUE;
for (int i : next) {
int clock, cClock;
if (i > cur) {
clock = cur + length - i;
cClock = i - cur;
}else {
clock = cur - i;
cClock = length - cur + i;
}
int goClock = dfs(ks, length, index + 1, map, steps + clock + 1, i, dp); // go clockwise
int goCClock = dfs(ks, length, index + 1, map, steps + cClock + 1, i, dp); // go counterclockwise
min = Math.min(min, Math.min(goClock, goCClock));
}

dp[cur][index] = min - steps; /* store the value for starting from index if we use cur from string ring*/
return min;
}
``````

}

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