How do I efficiently find the position of each letter on the alphabet board?

By using a hash table to store the row and column positions of each letter, you can instantly access the position of any letter in constant time.

What are the possible moves on the alphabet board?

The moves are right (R), left (L), up (U), and down (D), with each move followed by '!' to represent pressing the key.

Can I optimize the path calculation further?

Ensure you're calculating the minimal horizontal and vertical distance to reduce unnecessary movements. Avoid backtracking or extra steps.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the target string, since each letter lookup and move calculation takes constant time.

How does the board look for this problem?

The board is a 5x5 grid with the letters 'a' to 'z', arranged as ['abcde', 'fghij', 'klmno', 'pqrst', 'uvwxy', 'z'].

#1138

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

字母板上的路径

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0] 。在本题里，字母板为 board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"] ，如下所示。我们可以按下面的指令规则行动：如果方格存在， 'U'…

哈希表字符串

题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

如果方格存在，'U' 意味着将我们的位置上移一行；
如果方格存在，'D' 意味着将我们的位置下移一行；
如果方格存在，'L' 意味着将我们的位置左移一列；
如果方格存在，'R' 意味着将我们的位置右移一列；
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"

示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

提示：

1 <= target.length <= 100
target 仅含有小写英文字母。

lightbulb

解题思路

方法一：模拟

从起点 $(0, 0)$ 出发，模拟每一步的移动，将每一步的移动结果拼接到答案中。注意移动的方向遵循“左、上、右、下”的顺序。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $target$ 的长度，需要遍历字符串 $target$ 中的每一个字符。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        i = j = 0
        ans = []
        for c in target:
            v = ord(c) - ord("a")
            x, y = v // 5, v % 5
            while j > y:
                j -= 1
                ans.append("L")
            while i > x:
                i -= 1
                ans.append("U")
            while j < y:
                j += 1
                ans.append("R")
            while i < x:
                i += 1
                ans.append("D")
            ans.append("!")
        return "".join(ans)

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the length of the target string, as each letter's position lookup and move calculation is done in constant time. Space complexity is O(1) due to the fixed size of the board and hash table, since the hash table only stores the positions of 26 letters.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of the hash table for efficient letter position lookup.
question_mark
Look for the ability to optimize movement calculations and reduce unnecessary steps.
question_mark
Check if the candidate can maintain efficient space and time complexity while handling string manipulation.

warning

常见陷阱

外企场景

error
Overcomplicating the move calculation process, leading to inefficient or incorrect paths.
error
Forgetting to account for the exact movement required between rows and columns.
error
Not leveraging the hash table properly, leading to repeated scans of the board.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider an extended board where rows and columns are dynamically added.
arrow_right_alt
What if the board is provided as a list of strings where each row can vary in length?
arrow_right_alt
How would this approach change if the board contains more than one key per position?

help

常见问题

外企场景

继续练习

#1156 单字符重复子串的最大长度 #1160 拼写单词 #1169 查询无效交易