Minimum Distance to Type a Word Using Two Fingers
You have a keyboard layout in the X-Y 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 word 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 they do not count toward your total distance. Also, your two fingers do not have to start at the first letter or the first two letters.
Example 1
Input
word = "CAKE"Output
3One optimal way types C and A with one finger for cost 2, and K and E with the other finger for cost 1, for a total distance of 3.
Example 2
Input
word = "HAPPY"Output
6One optimal way types H, A, and Y with one finger for costs 0, 2, and 4, while the other finger types P twice for cost 0, totaling 6.
Constraints
- 2 <= word.length <= 300
- word consists of uppercase English letters.