题目描述

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。

• 例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。

坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。

样例

输入：word = "CAKE"
输出：3
解释： 
使用两根手指输入 "CAKE" 的最佳方案之一是： 
手指 1 在字母 'C' 上 -> 移动距离 = 0 
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2 
手指 2 在字母 'K' 上 -> 移动距离 = 0 
手指 2 在字母 'E' 上 -> 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1 
总距离 = 3

输入：word = "HAPPY"
输出：6
解释： 
使用两根手指输入 "HAPPY" 的最佳方案之一是：
手指 1 在字母 'H' 上 -> 移动距离 = 0
手指 1 在字母 'A' 上 -> 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2
手指 2 在字母 'P' 上 -> 移动距离 = 0
手指 2 在字母 'P' 上 -> 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0
手指 1 在字母 'Y' 上 -> 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4
总距离 = 6

限制

• 2 <= word.length <= 300
• 每个 word[i] 都是一个大写英文字母。

算法

(动态规划) $O(n |\Sigma|^2)$

1. 初始化任意两个字母的距离。
2. 设状态 $f(i, j, k)$ 表示当前完成了前 $i$ 个字母，当前第一根手指在字母 $j$ 上，第二根手指在字母 $k$ 上的最少步数。
3. 初始时，$f(0, j, k) = 0$，其余为正无穷。初始状态表示了，还没有进行任何操作时，两根手指在任意位置的花费都是 $0$。
4. 转移时，有两种情况，假设上一次手指的位置为 $j$ 和 $k$，待移动到的字母为 $t$。第一种是移动第一根手指，则 $f(i, t, k) = \min(f(i, t, k), f(i - 1, j, k) + dis(j, t)$；第二种是移动第二根手指，则 $f(i, j, t) = \min(f(i, j, t), f(i - 1, j, k) + dis(k, t)$。
5. 最终答案为 $\min(f(n, j, k))$。

时间复杂度

• 状态数为 $O(n |\Sigma|^2)$，每个状态的后续转移只有两种，故总时间复杂度为 $O(n |\Sigma|^2)$。

空间复杂度

• 需要额外 $n |\Sigma|^2$ 的空间存储状态，以及 $|\Sigma|^2$ 的数组存储任意两个字母的距离。
• 故空间复杂度为 $O(n |\Sigma|^2)$。

C++ 代码

const int N = 310, M = 26;
const int INF = 1000000000;

int dis[M][M];

auto init = []{
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++)
            dis[i][j] = abs(i / 6 - j / 6) + abs(i % 6 - j % 6);

    return 0;
}();

class Solution {
private:
    int f[N][M][M];

public:
    int minimumDistance(string word) {
        const int n = word.length();

        for (int j = 0; j < 26; j++)
            for (int k = 0; k < 26; k++)
                f[0][j][k] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++)
                for (int k = 0; k < 26; k++)
                    f[i][j][k] = INF;

            int t = word[i - 1] - 'A';

            for (int j = 0; j < 26; j++)
                for (int k = 0; k < 26; k++) {
                    f[i][t][k] = min(f[i][t][k], f[i - 1][j][k] + dis[j][t]);
                    f[i][j][t] = min(f[i][j][t], f[i - 1][j][k] + dis[k][t]);
                }
        }

        int ans = INF;

        for (int j = 0; j < 26; j++)
            for (int k = 0; k < 26; k++)
                ans = min(ans, f[n][j][k]);

        return ans;
    }
};