1320：二指输入的的最小距离（2027 分）

力扣第 171 场周赛第 4 题

题目

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

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

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

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

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

示例 1：

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

示例 2：

输入：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] 都是一个大写英文字母。

相似问题：

• 1974：使用特殊打字机键入单词的最少时间（1364 分）

分析

#1

令 f(a,b) 代表两根手指分别在位置 a,b 时的最小距离，递推即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

@cache
def cal(a,b):
    x1,y1 = divmod(a,6)
    x2,y2 = divmod(b,6)
    return abs(x1-x2)+abs(y1-y2)

class Solution:
    def minimumDistance(self, word: str) -> int:
        f = {(a,b):0 for a in range(26) for b in range(26)}
        for c in word:
            c = ord(c)-ord('A')
            g = defaultdict(lambda:inf)
            for (a,b),w in f.items():
                g[(a,c)] = min(g[(a,c)], cal(b,c)+w)
                g[(c,b)] = min(g[(c,b)], cal(a,c)+w)
            f = g
        return min(f.values())

259 ms

#2

• 注意到遍历到 word[i] 时必然有根手指在 word[i] 处，状态中无需记录该信息
• 因此，令 f(a) 代表另一根手指在位置 a 时的最小距离，进行递推

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

@cache
def cal(a,b):
    x1,y1 = divmod(a,6)
    x2,y2 = divmod(b,6)
    return abs(x1-x2)+abs(y1-y2)

class Solution:
    def minimumDistance(self, word: str) -> int:
        A = [ord(c)-ord('A') for c in word]
        f = [0]*26
        for a,b in pairwise(A):
            f = [min(f[c]+cal(a,b),f[b]+cal(a,c)) for c in range(26)]
        return min(f)

47 ms