LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers

, , , ,

Question

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x1,y1) and (x2,y2) is |x1 - x2| + |y1 - y2|.

Note that the initial positions of your two fingers are considered free so don’t count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Input: word = "HAPPY"
Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Input: word = "NEW"
Output: 3

Solution

For each character, we need to decide which finger we need to use and to explore different combinations. Also, we use memo array to cache.

Code

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
// time: O(n * 27 * 27) space: O(n * 27 * 27)
   public int minimumDistance(String word) {
       k = 26;// 作为初始的free状态
       int n = word.length();
       int[][][] memo = new int[n][27][27];
       for (int[][] arrs : memo) {
           for (int[] arr : arrs) Arrays.fill(arr, -1);
       }
       return dfs(word, 0, k, k, n, memo);
   }
   
   
   public int cost(int from, int to) {
       if (from == k) return 0;
       return Math.abs(from / 6 - to / 6) + Math.abs(from % 6 - to % 6);
   }
   
   // min cost to type word[i : n]. l是左手敲进去，r就是右手敲进去
   public int dfs(String word, int i, int l, int r, int n, int[][][] memo) {
       if (i == n) return 0;
       if (memo[i][l][r] != -1) return memo[i][l][r];
       int pos = word.charAt(i) - 'A';
       int res = Math.min(dfs(word, i + 1, pos, r, n, memo) + cost(l, pos), 
                          dfs(word, i + 1, l, pos, n, memo) + cost(r, pos));
       memo[i][l][r] = res;
       return res;
   }