Freedom Trail LeetCode solution in C++

1
class Solution {
2
 public:
3
  int n, m;
4
  vector<int> pos[26];
5
  int findRotateSteps(string ring, string key) {
6
    n = ring.size(), m = key.size();
7
    for (int i = 0; i < n; i++) pos[ring[i] - 'a'].push_back(i);
8
    vector<vector<int>> memo(n, vector<int>(m, INT_MAX));
9
    return helper(0, 0, memo, ring, key);
10
  }
11
  int helper(int i, int j, vector<vector<int>> &memo, string &ring, string &key) {
12
    if (j == m) return 0;
13
    if (memo[i][j] != INT_MAX) return memo[i][j];
14
    int best = INT_MAX;
15
    for (int &next : pos[key[j] - 'a']) {
16
      int diff = abs(i - next);
17
      best = min(best, min(diff, n - diff) + helper(next, j + 1, memo, ring, key));
18
    }
19
    return memo[i][j] = best + 1;
20
  }
21
};