# Most easy understandable solution with detail explaination

• ``````//Fast Solution : DP
//Transition Formula: dp[i][j] = Math.min(dp[i + 1][k1] + clockStep(k1, j), dp[i + 1][k2] + antiStep(k2, j));
//Time: O(m*n) 46 ms, 86%
public int findRotateSteps(String ring, String key) {
int n = ring.length();
int m = key.length();
int[][] dp = new int[m + 1][n];
int[][] clock = preproc(ring, 1), anti = preproc(ring, -1);
for (int i = m - 1; i >= 0; i--) {
int idx = key.charAt(i) - 'a';
for (int j = 0; j < n; j++) {
int k1 = clock[j][idx];
int k2 = anti[j][idx];
dp[i][j] = Math.min(dp[i + 1][k1] + (j - k1 + n) % n, dp[i + 1][k2] + (k2 - j + n) % n);
}
}

return dp[0][0] + m;
}
int[][] preproc(String r, int inc) {
int n = r.length();
int[][] ans = new int[n][26];
int[] map = new int[26];
for (int i = 0, j = 0; j < n * 2 - 1; ++j) {
map[r.charAt(i) - 'a'] = i;
for (int k = 0; k < 26; k++) {
ans[i][k] = map[k];
}
i = (i + inc + n) % n;
}
return ans;
}

//Solution: DFS + Memo

public int findRotateSteps(String ring, String key) {
Map<String, Integer> memo = new HashMap<>();
return dfs(memo, ring, key, 0);
}

//memo: key is ring & index as a string, value is min steps;
//index: is index of key
private int dfs(Map<String, Integer> memo, String ring, String key, int index) {
if (index >= key.length()) {
return 0;
}

//Fetch memory
String memoKey = ring + index;
if (memo.containsKey(memoKey)) {
return memo.get(memoKey);
}

//DFS
char c = key.charAt(index);
int forwardPos = getPosition(ring, c);//forward position
int backwardPos = getBackPosition(ring, c);//backward position

//forward steps and backward steps
int forwardSteps = 1 + forwardPos
+ dfs(memo, ring.substring(forwardPos) + ring.substring(0, forwardPos), key, index + 1);
int backwardSteps = 1 + ring.length() - backwardPos
+ dfs(memo, ring.substring(backwardPos) + ring.substring(0, backwardPos), key, index + 1);
int steps = Math.min(forwardSteps, backwardSteps);

//Memorize
memo.put(memoKey, steps);

return steps;
}

private int getPosition(String ring, char c) {
return ring.indexOf(c);
}

private int getBackPosition(String ring, char c) {
return ring.length() - 1 - new StringBuffer(ring).reverse().toString().indexOf(c);
}``````

• Best DP solution.

• Easy understandable DFS solution.

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