What is the optimal approach to solve the 'Minimum Distance to Type a Word Using Two Fingers' problem?

The optimal solution involves dynamic programming where you track the positions of both fingers and minimize the distance between the current and next letter in the word.

How does dynamic programming apply to this problem?

Dynamic programming helps by modeling the finger positions as states and minimizing the movement cost at each step while transitioning through different positions.

What is the complexity of the solution for the 'Minimum Distance to Type a Word Using Two Fingers' problem?

The time complexity is O(n * 26 * 26), where n is the word length, and the space complexity is O(n * 26 * 26), due to the state space for both fingers.

How can I optimize my solution for the minimum distance typing problem?

Focus on minimizing the total distance by efficiently managing finger placements at each step and considering all possible transitions between letters.

Are there any variants of the 'Minimum Distance to Type a Word Using Two Fingers' problem?

Variants include increasing the number of fingers, expanding the keyboard layout, or changing the grid arrangement, which affects the state space and solution complexity.

#1320

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

二指输入的的最小距离

二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。例如字母 A 位于坐标 (0,0) ，字母 B 位于坐标 (0,1) ，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1) 。给你一个待输入字符串 word ，请你计算并返回在仅使用两根手指…

字符串动态规划

题目描述

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

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

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

坐标 (x₁,y₁) 和 (x₂,y₂) 之间的距离是 |x₁ - x₂| + |y₁ - y₂|。

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

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j][k]$ 表示输入完 $\textit{word}[i]$ ，且手指 $1$ 位于位置 $j$ ，手指 $2$ 位于位置 $k$ 时，最小的移动距离。这里的位置 $j$ 和 $k$ 表示的是字母对应的数字，取值范围为 $[0,..25]$ 。初始时 $f[i][j][k]=\infty$ 。

我们实现一个函数 $\textit{dist}(a, b)$ ，表示位置 $a$ 和位置 $b$ 之间的距离，即 $\textit{dist}(a, b) = |\frac{a}{6} - \frac{b}{6}| + |a \bmod 6 - b \bmod 6|$ 。

接下来，我们考虑输入 $\textit{word}[0]$ ，即只有一个字母的的情况，此时有两种选择：

手指 $1$ 位于 $\textit{word}[0]$ 所在的位置，手指 $2$ 位于任意位置，此时 $f[0][\textit{word}[0]][k] = 0$ ，其中 $k \in [0,..25]$ 。
手指 $2$ 位于 $\textit{word}[0]$ 所在的位置，手指 $1$ 位于任意位置，此时 $f[0][k][\textit{word}[0]] = 0$ ，其中 $k \in [0,..25]$ 。

然后我们考虑输入 $\textit{word}[1,..n-1]$ ，我们记上一个字母和当前字母所在的位置分别为 $a$ 和 $b$ ，接下来我们进行分情况讨论：

如果当前手指 $1$ 位于位置 $b$ ，我们枚举手指 $2$ 的位置 $j$ ，假如上一个位置 $a$ 也是手指 $1$ 的位置，那么此时有 $f[i][b][j]=\min(f[i][b][j], f[i-1][a][j]+\textit{dist}(a, b))$ 。如果手指 $2$ 的位置与上一个位置 $a$ 相同，即 $j=a$ ，那么我们枚举上一个位置的手指 $1$ 所在的位置 $k$ ，此时有 $f[i][j][j]=\min(f[i][b][j], f[i-1][k][a]+\textit{dist}(k, b))$ 。

同理，如果当前手指 $2$ 位于位置 $b$ ，我们枚举手指 $1$ 的位置 $j$ ，假如上一个位置 $a$ 也是手指 $2$ 的位置，那么此时有 $f[i][j][b]=\min(f[i][j][b], f[i-1][j][a]+\textit{dist}(a, b))$ 。如果手指 $1$ 的位置与上一个位置 $a$ 相同，即 $j=a$ ，那么我们枚举上一个位置的手指 $2$ 所在的位置 $k$ ，此时有 $f[i][j][b]=\min(f[i][j][b], f[i-1][a][k]+\textit{dist}(k, b))$ 。

最后，我们枚举最后一个位置的手指 $1$ 和手指 $2$ 所在的位置，取最小值即为答案。

时间复杂度 $O(n \times |\Sigma|^2)$ ，空间复杂度 $O(n \times |\Sigma|^2)$ 。其中 $n$ 为字符串 $\textit{word}$ 的长度，而 $|\Sigma|$ 为字母表的大小，本题中 $|\Sigma|=26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def minimumDistance(self, word: str) -> int:
        def dist(a: int, b: int) -> int:
            x1, y1 = divmod(a, 6)
            x2, y2 = divmod(b, 6)
            return abs(x1 - x2) + abs(y1 - y2)

        n = len(word)
        f = [[[inf] * 26 for _ in range(26)] for _ in range(n)]
        for j in range(26):
            f[0][ord(word[0]) - ord('A')][j] = 0
            f[0][j][ord(word[0]) - ord('A')] = 0
        for i in range(1, n):
            a, b = ord(word[i - 1]) - ord('A'), ord(word[i]) - ord('A')
            d = dist(a, b)
            for j in range(26):
                f[i][b][j] = min(f[i][b][j], f[i - 1][a][j] + d)
                f[i][j][b] = min(f[i][j][b], f[i - 1][j][a] + d)
                if j == a:
                    for k in range(26):
                        t = dist(k, b)
                        f[i][b][j] = min(f[i][b][j], f[i - 1][k][a] + t)
                        f[i][j][b] = min(f[i][j][b], f[i - 1][a][k] + t)
        a = min(f[n - 1][ord(word[-1]) - ord('A')])
        b = min(f[n - 1][j][ord(word[-1]) - ord('A')] for j in range(26))
        return int(min(a, b))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for familiarity with dynamic programming and state transitions.
question_mark
Assess whether the candidate can optimize the finger movements to minimize the total distance.
question_mark
Evaluate how well the candidate understands the structure of the problem and the importance of considering both fingers simultaneously.

warning

常见陷阱

外企场景

error
Ignoring the need to minimize the total distance for both fingers at every step.
error
Failing to optimize the state transitions between different letter positions.
error
Not considering edge cases with small word lengths or repeated characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than two fingers to type, which changes the state space.
arrow_right_alt
Increasing the size of the keyboard to include lowercase letters, affecting the state space.
arrow_right_alt
Changing the grid layout of the keyboard to test different spatial arrangements.

help

常见问题

外企场景

继续练习

#1312 让字符串成为回文串的最少插入次数 #1278 分割回文串 III #1255 得分最高的单词集合