Freedom Trail LeetCode solution in Java

1
class Solution {
2
  public int findRotateSteps(String ring, String key) {
3
    Map<Character, TreeSet<Integer>> locMap = new HashMap<>();
4
    for (int i = 0; i < ring.length(); i++) {
5
      locMap.computeIfAbsent(ring.charAt(i), o -> new TreeSet<>()).add(i);
6
    }
7
    return dfs(0, 0, locMap, key, new int[key.length()][ring.length()]);
8
  }
9

10
  private int dfs(
11
      int cur, int where, Map<Character, TreeSet<Integer>> locMap, String key, int[][] memo) {
12
    if (cur == key.length()) { // the end
13
      return 0;
14
    }
15
    if (memo[cur][where] > 0) { // have computed [cur, end) already.
16
      return memo[cur][where];
17
    }
18
    TreeSet<Integer> idx = locMap.get(key.charAt(cur));
19
    if (idx.contains(where)) { // greedily take this if it is already matched
20
      return memo[cur][where] = dfs(cur + 1, where, locMap, key, memo) + 1;
21
    }
22
    Integer hi = idx.higher(where); // otherwise, we can take the higher key
23
    Integer lo = idx.lower(where); // or, the lower key
24
    if (hi == null) { // if no higher key, it becomes the lowest key.
25
      hi = idx.first();
26
    }
27
    if (lo == null) { // if no lower key, it becomes the highest key.
28
      lo = idx.last();
29
    }
30
    int hcost =
31
        dfs(cur + 1, hi, locMap, key, memo)
32
            + (hi > where ? hi - where : memo[0].length - where + hi);
33
    int lcost =
34
        dfs(cur + 1, lo, locMap, key, memo)
35
            + (lo < where ? where - lo : where + memo[0].length - lo);
36
    return memo[cur][where] = Math.min(hcost, lcost) + 1;
37
  }
38
}