1138. 字母板上的路径

ITCharge大约 5 分钟

---

1138. 字母板上的路径

标签：哈希表、字符串
难度：中等

题目链接

1138. 字母板上的路径 - 力扣

题目大意

描述：给定一个字符串 $target$ ，代表我们想要拼出的字母序列。

字母板是一块 6 行 5 列的板子，上面按顺序排列着字母：

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

注意最后一行只有字母 z 一个，其他行都是 5 个字母。

一开始我们的指针在位置 $(0, 0)$ ，也就是左上角的字母 a 上。我们可以通过以下指令移动指针：

U：向上移一行（如果目标位置有字母的话）
D：向下移一行（如果目标位置有字母的话）
L：向左移一列（如果目标位置有字母的话）
R：向右移一列（如果目标位置有字母的话）
!：把当前位置的字母添加到答案中

要求：输出一个指令序列，使得我们的指针依次走到 $target$ 中每个字母的位置，并用 ! 把字母记录下来。要求指令序列尽可能短（返回任意一种最短路径即可）。

说明：

$1 \le target.length \le 10^{3}$ 。
$target$ 仅含有小写英文字母。

示例：

示例 1：

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

示例 2：

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

解题思路

思路 1：模拟法（按坐标一步步走）

这道题其实就是一个「按图索骥」的过程。我们可以把字母板想象成一张地图，每个字母都有一个确定的坐标（第几行第几列）。我们要做的，就是从当前位置出发，一步步移动到目标字母的位置，然后按 ! 记录下来，接着再走向下一个字母。

这里的难点只有一个：字母 z 比较特殊，它孤零零地待在最后一行的第一列，周围没有别的字母。 如果移动顺序不对，可能经过没有字母的区域（越界）。所以需要特殊处理。

步骤拆解：

建立字母到坐标的映射。 每个字母在字母板上的位置可以用「行号 = (字母序号 ÷ 5) 的整数部分，列号 = (字母序号 ÷ 5) 的余数」来计算。字母序号就是把 a 当作 0、b 当作 1……z 当作 25。
从起始位置出发。 初始位置是 a 的坐标，即第 0 行第 0 列。
逐个处理目标字符串中的每个字母：
- 先算出目标字母的行号和列号。
- 然后从当前位置移动到目标位置。
- 移动的时候要留意：如果当前位置是 z（第 5 行第 0 列），或者目标位置是 z，需要调整移动顺序，避免走到板子外面去。
关于 z 的特殊处理规则（只需记住两个口诀）：
- 从别处走向 z 时：先左移（如果当前在右边），再上移（如果当前在下面），再下移，最后右移。因为 z 在最下面一行却只有第一列，从右边或下面过来时，必须先走到安全的路径再往下。
- 从 z 走向别处时：先上移（离开最后一行！），再处理其他方向。如果不先上移，向左或向右都可能走到不存在的格子。

为什么这个顺序能保证不越界？
因为字母板除了最后一行只有 z 一个字母外，其他格子都是完整的。所以只要保证：到达 z 之前先调整好列，离开 z 之后先离开最后一行，就不会走到空白区域。

思路 1：代码

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        # 辅助函数：给定字母，返回它在字母板上的行列坐标
        def get_pos(ch):
            idx = ord(ch) - ord('a')  # 把字母转成数字，a=0, b=1, ..., z=25
            return idx // 5, idx % 5  # 行号 = 除以5取整，列号 = 除以5取余数
        
        res = []               # 收集指令
        cur_row, cur_col = 0, 0  # 指针当前位置，一开始在 (0,0) 也就是字母 a
        
        # 逐个处理目标字符串中的每个字母
        for ch in target:
            tar_row, tar_col = get_pos(ch)  # 目标字母的行列
            
            # 情况1：目标字母是 z（需要特殊处理移动顺序）
            if ch == 'z':
                # 如果当前在 z 的右边，先向左移
                if cur_col > tar_col:
                    res.append('L' * (cur_col - tar_col))
                    cur_col = tar_col
                # 如果当前在 z 的下边（其实不会发生，但为了统一逻辑），先向上移
                if cur_row > tar_row:
                    res.append('U' * (cur_row - tar_row))
                    cur_row = tar_row
                # 如果当前在 z 的上边，向下移
                if cur_row < tar_row:
                    res.append('D' * (tar_row - cur_row))
                    cur_row = tar_row
                # 最后如果当前在 z 的左边，向右移
                if cur_col < tar_col:
                    res.append('R' * (tar_col - cur_col))
                    cur_col = tar_col
            else:
                # 情况2：目标字母不是 z
                # 如果当前位置是 z（在最后一行），先向上移，避免越界
                if cur_row > tar_row:
                    res.append('U' * (cur_row - tar_row))
                    cur_row = tar_row
                # 向下移
                if cur_row < tar_row:
                    res.append('D' * (tar_row - cur_row))
                    cur_row = tar_row
                # 向左移
                if cur_col > tar_col:
                    res.append('L' * (cur_col - tar_col))
                    cur_col = tar_col
                # 向右移
                if cur_col < tar_col:
                    res.append('R' * (tar_col - cur_col))
                    cur_col = tar_col
            
            # 到达目标字母后，用 ! 记录下来
            res.append('!')
        
        # 把指令列表拼接成字符串返回
        return ''.join(res)

思路 1：复杂度分析

时间复杂度： $O(n)$ 。其中 $n$ 是字符串 $target$ 的长度。对于每个字母，我们最多移动 4 步（上、下、左、右），所以总步数和 $n$ 成正比。用人话说就是：字符串多长，我们就处理多少次，每次处理花固定时间。
空间复杂度： $O(1)$ 。除了存储结果的指令序列外，我们只用了几个固定大小的变量，不随输入规模增大。