Minimum Distance to Type a Word Using Two Fingers LeetCode solution in C++

1
class Solution {
2
 public:
3
  string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
4
  unordered_map<char, pair<int, int>> m;
5
  int distCalc(char a, char b) {
6
    pair<int, int> p_a = m[a];
7
    pair<int, int> p_b = m[b];
8

9
    int x_diff = abs(p_a.first - p_b.first);
10
    int y_diff = abs(p_a.second - p_b.second);
11

12
    return x_diff + y_diff;
13
  }
14
  int dp[301][27][27];
15
  int minDist(string word, int i, char finger1_char, char finger2_char) {
16
    if (i == word.size()) return 0;
17

18
    if (dp[i][finger1_char - 'A'][finger2_char - 'A'] != -1)
19
      return dp[i][finger1_char - 'A'][finger2_char - 'A'];
20

21
    // finger1
22
    int op1 = (finger1_char == '[' ? 0 : distCalc(finger1_char, word[i])) +
23
              minDist(word, i + 1, word[i], finger2_char);
24

25
    // finger2
26
    int op2 = (finger2_char == '[' ? 0 : distCalc(finger2_char, word[i])) +
27
              minDist(word, i + 1, finger1_char, word[i]);
28

29
    return dp[i][finger1_char - 'A'][finger2_char - 'A'] = min(op1, op2);
30
  }
31
  int minimumDistance(string word) {
32
    // each letter has choice to be clicked by finger 1 or 2
33

34
    int row = -1;
35
    for (int i = 0; i < alpha.length(); i++) {
36
      int col = i % 6;
37
      if (col == 0) row++;
38
      m[alpha[i]] = {row, col};
39
    }
40
    memset(dp, -1, sizeof(dp));
41
    return minDist(word, 0, '[', '[');
42
  }
43
};