# 1320. Minimum Distance to Type a Word Using Two Fingers    • Time: $O(27^2n) = O(n)$
• Space: $O(27^2n) = O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: int minimumDistance(string word) { // dp[i][j][k] := the minimum distance to type the word, where the left // finger is on the i-th letter, the right finger is on the j-th letter, and // the words[0..k) have been written dp.resize(27, vector>(27, vector(word.length(), -1))); return minimumDistance(word, 26, 26, 0); } private: vector>> dp; int minimumDistance(const string& word, int i, int j, int k) { if (k == word.length()) return 0; if (dp[i][j][k] != -1) return dp[i][j][k]; const int next = word[k] - 'A'; const int moveLeft = dist(i, next) + minimumDistance(word, next, j, k + 1); const int moveRight = dist(j, next) + minimumDistance(word, i, next, k + 1); return dp[i][j][k] = min(moveLeft, moveRight); } int dist(int a, int b) { if (a == 26) // the first hovering state return 0; const int x1 = a / 6; const int y1 = a % 6; const int x2 = b / 6; const int y2 = b % 6; return abs(x1 - x2) + abs(y1 - y2); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public int minimumDistance(String word) { // dp[i][j][k] := the minimum distance to type the word, where the left // finger is on the i-th letter, the right finger is on the j-th letter, and // the words[0..k) have been written dp = new Integer[word.length()]; return minimumDistance(word, 26, 26, 0); } private Integer[][][] dp; private int minimumDistance(final String word, int i, int j, int k) { if (k == word.length()) return 0; if (dp[i][j][k] != null) return dp[i][j][k]; final int next = word.charAt(k) - 'A'; final int moveLeft = dist(i, next) + minimumDistance(word, next, j, k + 1); final int moveRight = dist(j, next) + minimumDistance(word, i, next, k + 1); return dp[i][j][k] = Math.min(moveLeft, moveRight); } private int dist(int a, int b) { if (a == 26) // the first hovering state return 0; final int x1 = a / 6; final int y1 = a % 6; final int x2 = b / 6; final int y2 = b % 6; return Math.abs(x1 - x2) + Math.abs(y1 - y2); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def minimumDistance(self, word: str) -> int: def dist(a: int, b: int) -> int: if a == 26: # the first hovering state return 0 x1, y1 = a // 6, a % 6 x2, y2 = b // 6, b % 6 return abs(x1 - x2) + abs(y1 - y2) # dp(i, j, k) := the minimum distance to type the word, where the left # finger is on the i-th letter, the right finger is on the j-th letter, and # the words[0..k) have been written @functools.lru_cache(None) def dp(i: int, j: int, k: int) -> int: if k == len(word): return 0 nxt = ord(word[k]) - ord('A') moveLeft = dist(i, nxt) + dp(nxt, j, k + 1) moveRight = dist(j, nxt) + dp(i, nxt, k + 1) return min(moveLeft, moveRight) return dp(26, 26, 0)