# Java Clear Solution, dfs+memoization

• Hi There! The key point in the problem is to make decision whether to move clockwise or anticlockwise. Actually to get optimal answer, we have to move clockwise for some characters of `key` and anti-clockwise for others. If apply brute force, then for each position in `key` we have two options,

• Search for the character clockwise
• Search for the character anti-clockwise

To find optimal answer we need to try both options and get minimum of them. Thus, we obtain `dfs solution` for the problem. But, there are duplicate calculation for some positions. Therefore, we need to memorize `states`. The `state` is defined by position of the`ring` and the index of character in the `key`. This way, we can avoid calculating number of steps for the same state. Code will clarify the idea more.

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

private int findPos(String ring, char ch){ // find first occurrence clockwise
return ring.indexOf(ch);
}

private int findBackPos(String ring, char ch){ //find first occurrence  anti-clockwise
if(ring.charAt(0) == ch) return 0;
for(int i = ring.length()-1;i>0;i--){
if(ring.charAt(i) == ch) return i;
}
return 0;
}

private int dfs(String ring, String key, int i){
if(i == key.length()) return 0;
int res = 0;
char ch = key.charAt(i);
if(memo.containsKey(ring) && memo.get(ring).containsKey(i)) return memo.get(ring).get(i);
int f = findPos(ring, ch);
int b = findBackPos(ring, ch);
int forward = 1+f+dfs(ring.substring(f)+ring.substring(0, f), key, i+1);
int back = 1+ring.length()-b + dfs(ring.substring(b)+ring.substring(0, b),key, i+1);
res = Math.min(forward, back);
Map<Integer, Integer> ans = memo.getOrDefault(ring, new HashMap<>());
ans.put(i, res);
memo.put(ring, ans);
return res;
}
}``````

• I think your memoization may be a little bit waste of space, the state can be determined by only the 12:00 position of ring and the index of key.

• @zzwcsong Agree:=)

• @ZhassanB How can you prove find the first occurrence of a character (clock or anti-clockwise) will yield the optimal solution?

• @caofang I think this is a top-down approach. Assume we have already solved the first K-1 characters, then for the last character, we only need to find the closest matched character from clockwise direction and anti-clockwise direction.

• This post is deleted!

• This post is deleted!

• Here is my version of DFS+memoization with comments:

``````public class Solution {
// map: for every unique char in ring, find all its occurances.
Map<Character, Set<Integer>>map;

// memo[i][j]: the min steps required when
// 1) the jth element of ring is at the 12:00
// 2) the remaining key is key.substring(i)
// this is for memorioation purpose
int[][] memo;
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();

map = new HashMap<>();
for (int i=0;i<n;i++){
char c=ring.charAt(i);
map.putIfAbsent(c, new HashSet<>());
}

// initialize the memo: -1 represents not calculated yet.
memo = new int[m][n];
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
memo[i][j]=-1;

// "+m" is the m spelling steps
return helper(ring, key, 0, 0)+m;
}

private int helper(String ring, String key, int x, int y){
if (x==key.length()) return 0;
if (memo[x][y]>=0) return memo[x][y];

int min=Integer.MAX_VALUE;
for (int k:map.get(key.charAt(x))){
int diff=Math.abs(k-y);
int step=Math.min(diff, ring.length()-diff);
min=Math.min(min, step+helper(ring, key, x+1, k));
}
memo[x][y]=min;
return min;
}
}
``````

• 老铁们, C++ version:

``````class Solution {
public:
int findRotateSteps(string ring, string key) {
int rLen = ring.size(), kLen = key.size();
// indices for each unique char (So that we could know where to rotate to quickly)
unordered_map<char, unordered_set<int> > mp;
for (int i = 0; i < rLen; ++i) {
mp[ring[i]].insert(i);
}
// memo[rIdx][kIdx]:
// rIdx: index in ring which points to 12:00
// kIdx: index in key
vector<vector<int> > memo(rLen, vector<int>(kLen, 0));
return dfs(ring, key, mp, memo, 0, 0) + kLen;
}

int dfs(string &ring, string &key, unordered_map<char, unordered_set<int> > &mp,
vector<vector<int> > &memo, int rIdx, int kIdx) {
if (kIdx == key.size()) { return 0; }
if (memo[rIdx][kIdx]) { return memo[rIdx][kIdx]; }
int ans = INT_MAX;
for (int nextIdx : mp[key[kIdx]]) {
// idx is the index for the NEXT char we want to find
// we could go forward `diff` or backward `rLen - diff`, pick the minimum one
int diff = abs(nextIdx - rIdx);
int step = min(diff, (int)ring.size() - diff);
ans = min(ans, dfs(ring, key, mp, memo, nextIdx, kIdx + 1) + step);
}
memo[rIdx][kIdx] = ans;
return ans;
}

};
``````

• @zorro77 Brilliant!

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