You have a keyboard layout as shown above 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 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 do not 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:
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
Example 2:
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
Constraints:
2 <= word.length <= 300
word consists of uppercase English letters.
這題給我們一個英文字母表與待輸入字串 words，
我們有兩隻手指 A, B 可以拿來打字，
題目希望我們找到手指打出 words 的最短移動路徑。
這題我有想到要用 DP，
但這次卡到的點是怎麼切換兩隻手指？
要怎麼蒐集另外一隻手指在上一個、上上個字元的狀態？
我看了一下別人的解答（＃，
核心概念是收集所有可能。
開一個二維陣列 DP，
第一個維度大小是 N，也就是 words 的長度；
第二個維度大小是 26，代表手指指到這個位置。
這個 DP 陣列最重要的用途就是把任何手指從上一個可能的路徑裡面收集過來，
因為有一個待用手指。
假設你上一個動作用 A 打，
現在想換手用 B，prev 迴圈邏輯就是幫 B 找一個歷史最短路徑。
今天程式碼太長了，先不放。
計算複雜度：O(N)
-> 因為 26 是常數，兩個迴圈其實其中一輪才會觸發，所以只做到 O(52*N) ~= O(N)
空間複雜度：O(1)
-> 我把空間優化到滾動 DP了，所以只有兩層 DP O(2*26) ~= O(1)
Github程式碼：
