[LeetCode] 1320. Minimum Distance to Type a Word Using Two Fingers 二指输入的的最小距离

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.

这道题说是让在一个数字键盘上输入一个单词，这不由得让博主想起了在 Roku 电视机上连 wifi 的痛苦经历，用遥控器来输入特别长的 wifi 密码是一件很痛苦的事情，这时候就特别想要一台触屏电视机。这道题虽然说是用两根手指，但实际上还是跟遥控器输入方式类似，要一个一个的移动光标，这里说是两根手指可以放在任意的位置，问最少要移动多少个位置才能输入整个单词。这种数组求极值的题目根据以往的经验大概率是要用动态规划 Dynamic Programming 来做的，那么首先来考虑考虑 DP 该如何定义吧。由于手指会不停的移动，所以每个状态中需要包括两根手指的位置信息，同时还要知道当前已经敲到单词中的哪个字母了，这样就需要一个三维数组，其中 dp[i][j][k] 就表示当前左手指在位置i，右手指在位置j，且当前要敲出的字母是 word[k]，敲完剩余所有字母所需的最小移动次数。注意这里的位置不是二维坐标，而是个一维数字，由于知道键盘的宽度为6，所以可以很容易的将其转为二维坐标 (n/6, n%6)。

接下来就要分析状态转移方程了，由于知道了下一个要去的位置是k，这里只需要看到底是左手指划过去近还是右手指划过去近，需要都计算一下，并取二者中的较小值。倘若是左手指划过去，需要计算左手指划过去的距离，同时需要加上下一个状态的 dp 值，这里可以对下个状态调用递归函数，此时左手指在新的位置，右手位置不变，pos 自增1，同理，需要计算右手指划过去的距离，同时需要加上下一个状态的 dp 值，这里可以对下个状态调用递归函数，此时右手指在新的位置，左手位置不变，pos 自增1。计算两个位置间的距离可以放到一个子函数中计算，方法其实就是计算两点之间曼哈顿距离，把横纵坐标的差的绝对值加起来就可以了。将一维数字转位二维坐标的方法前面已经讲过了，注意这里还有个判断，若 from 为 26，就直接返回0，这是为何呢？键盘上一共只有 26 个字母，一维数字为0到 25，所以 26 的位置上是空白的，起始时把两个手指都放到空白的位置，由于最优解的起始位置一定不会在空白位置，则第一次移动手指的距离就不能被加到 dp 值中，所以判定起始位置是 26 的话，直接返回0，代码如下：

解法一：

class Solution {
public:
    int minimumDistance(string word) {
        vector<vector<vector<int>>> dp(27, vector<vector<int>>(27, vector<int>(301, -1)));
        return dfs(word, 26, 26, 0, dp);
    }
    int dfs(string word, int left, int right, int pos, vector<vector<vector<int>>>& dp) {
        if (pos >= word.size()) return 0;
        if (dp[left][right][pos] == -1) {
            int to = word[pos] - 'A';
            dp[left][right][pos] = min(cost(left, to) + dfs(word, to, right, pos + 1, dp), cost(right, to) + dfs(word, left, to, pos + 1, dp));
        }
        return dp[left][right][pos];
    }
    int cost(int from, int to) {
        return from == 26 ? 0 : abs(from / 6 - to / 6) + abs(from % 6 - to % 6);
    }
};

我们可以对空间进行优化，对于每一个状态来说，总是会有一只手指会放在当前的字母上，而且会移动到下一个字母，至于到底是左手指还是右手指并不需要关心。所以说只需要记录上一个状态的手指位置就行了，这里只需要一个二维 dp 数组，其中 dp[i][j] 表示当前手指在位置i，且当前要敲出的字母是 word[j]，敲完剩余所有字母所需的最小移动次数。状态转移方程和之前没有太大的区别，取出当前要到的字母位置 to 和上次的字母位置 last，当前手指所在的位置是 other，那么到达 to 的位置就有两种方式，一种是从 last 过去，那么 other 上的手指保持不变，另一种是从 other 上过去，则 last 上的手指保持不变，参见代码如下：

解法二：

class Solution {
public:
    int minimumDistance(string word) {
        vector<vector<int>> dp(27, vector<int>(301, -1));
        return dfs(word, 26, 1, dp);
    }
    int dfs(string word, int other, int pos, vector<vector<int>>& dp) {
        if (pos >= word.size()) return 0;
        if (dp[other][pos] == -1) {
            int to = word[pos] - 'A', last = word[pos - 1] - 'A';
            dp[other][pos] = min(cost(last, to) + dfs(word, other, pos + 1, dp), cost(other, to) + dfs(word, last, pos + 1, dp));
        }
        return dp[other][pos];
    }
    int cost(int from, int to) {
        return from == 26 ? 0 : abs(from / 6 - to / 6) + abs(from % 6 - to % 6);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1320

类似题目：

Minimum Time to Type Word Using Special Typewriter

参考资料：

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/description/

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/solutions/477659/4-dp-solutions/

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/solutions/477652/java-c-python-1d-dp-o-1-space/

LeetCode All in One 题目讲解汇总(持续更新中…)

原文地址：http://www.cnblogs.com/grandyang/p/16910212.html