leetcode 周赛 171 5310. 二指输入的的最小距离 Minimum Distance to Type a Word Using Two Fingers

目录

1. 解答
   1. 准备
   2. 动规
      1. 初始状态
      2. 状态转移方程
      3. 结果
2. 其他

赛题链接 英文赛题 题库题目

二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 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

示例 3：

输入：word = "NEW"
输出：3

示例 4：

输入：word = "YEAR"
输出：7

提示：

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

解答

思路

我自己没做出来，学习了比赛排行榜上第一页的 suibianfahui 的代码。这个代码是我理解以后自己写的。原来和原代码相同。

准备

定义一个字母位置表，再定义一个函数 find_distance 查找任意两个字母间距离

动规

mapx[f1, f2] = setp

mapx 是一个字典，

f1 代表当前状态第一个手指的位置，f2 是第二个手指的位置， None 代表这个手指还没用过

setp 是现在一共移动了多少距离。

初始状态

mapx[单词第一个字母，None] = 0 代表我用第一个手打了第一个字母，第二个手没动，一共移动 0 步

状态转移方程

从第二个字母开始遍历单词，

对每一个字母要检查\上一步**所有的状态（因为只需要上一步，所以不用 dp 数组，每次都覆盖上一次的结果就可以了）

对每个状态，尝试用第一个手指打当前字母和用第二个手指打当前字母

结果

最后返回 map 中最小值就可以了。

代码

class Solution:
    def minimumDistance(self, word: str) -> int:
        if len(word) == 2: # 如果只有两个字母，不需要移动
            return 0
        # 字母位置表
        pos = {}
        ch = ord('A')
        for i in range(5):
            for j in range(6):
                pos[chr(ch)] = (i, j)
                if ch == ord('Z'): break
                ch += 1
        #print(pos)
        # {'A': (0, 0), 'B': (0, 1), 'C': (0, 2), 'D': (0, 3), 'E': (0, 4), 'F': (0, 5), 'G': (1, 0), 'H': (1, 1), 'I': (1, 2), 'J': (1, 3), 'K': (1, 4), 'L': (1, 5), 'M': (2, 0), 'N': (2, 1), 'O': (2, 2), 'P': (2, 3), 'Q': (2, 4), 'R': (2, 5), 'S': (3, 0), 'T': (3, 1), 'U': (3, 2), 'V': (3, 3), 'W': (3, 4), 'X': (3, 5), 'Y': (4, 0), 'Z': (4, 1)}
        def find_distance(a, b): # 求 a， b 两个字母距离
            if a == None: 
                return 0
            return abs(pos[a][0] - pos[b][0]) + abs(pos[a][1] - pos[b][1])
        
        mapx = {}
        mapx[(word[0], None)] = 0 # map[(a, b)] = setp 代表 第一个手指目前在 a 上， 第二个手指在 b 上， 步数为 setp
                                  # None 代表这个手指还没用过
        for cur in word[1:]:
            next_map = {}
            for finger1, finger2 in mapx:
                f1_dis = find_distance(finger1, cur) # 手指 1 到当前字母的距离
                f2_dis = find_distance(finger2, cur) # 手指 2 到当前字母的距离
                new_state1 = (cur, finger2) # 第一个手指按当前字母（当然第二个手指的状态不变）
                new_state2 = (finger1, cur) # 第二个手指按当前字母
                for new_state, dis in ((new_state1, f1_dis), (new_state2, f2_dis)):
                    if new_state in next_map:
                        next_map[new_state] = min(mapx[(finger1, finger2)] + dis, next_map[new_state])
                    else:
                        next_map[new_state] = mapx[(finger1, finger2)] + dis
            mapx = next_map
        return min(mapx.values())

其他

打印出题目中的字母排列：

amap = []
l = []
for i in range(ord('A'), ord('Z') + 1):
    l.append(chr(i))
    if len(l) == 6:
        amap.append(l)
        l = []
amap.append(l)
for l in amap:
    print(l)

['A', 'B', 'C', 'D', 'E', 'F']
['G', 'H', 'I', 'J', 'K', 'L']
['M', 'N', 'O', 'P', 'Q', 'R']
['S', 'T', 'U', 'V', 'W', 'X']
['Y', 'Z']

题目要求输入一个单词，也就是一个字母序列，要求用两个手指，所以我们的任务是：把一个单词序列分成两个子序列，并使手指移动次数最少。