字母板上的路径

标签: 哈希表字符串

难度: Medium

我们从一块字母板上的位置 (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 仅含有小写英文字母。

Submission

运行时间: 28 ms

内存: 0.0 MB

class Solution:
    def alphabetBoardPath(self, target):
        board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]
        char_dict = {}
        for i in range(len(board)):
            for j in range(len(board[i])):
                char_dict[board[i][j]] = (i, j)
        target = 'a' + target
        res = []
        for i in range(1, len(target)):
            diff = [char_dict[target[i]][0] - char_dict[target[i - 1]][0], \
                   char_dict[target[i]][1] - char_dict[target[i - 1]][1]]
            if target[i] != 'z':
                if diff[0] > 0:
                    res += diff[0] * ['D']
                elif diff[0] < 0:
                    res += -diff[0] * ['U']
                if diff[1] > 0:
                    res += diff[1] * ['R']
                elif diff[1] < 0:
                    res += -diff[1] * ['L']
            else:
                if diff[1] > 0:
                    res += diff[1] * ['R']
                elif diff[1] < 0:
                    res += -diff[1] * ['L']
                if diff[0] > 0:
                    res += diff[0] * ['D']
                elif diff[0] < 0:
                    res += -diff[0] * ['U']
            res.append('!')
        return ''.join(res)

Explain

题解首先将字母板上每个字符的位置存储到字典 char_dict 中，键为字符，值为其位置坐标 (行, 列)。然后，为了简化代码逻辑，将目标字符串 target 前加上字符 'a'，表示从 'a' 开始的路径。接下来，遍历 target 的每个字符，计算从前一个字符到当前字符的行列位置差 diff。根据 diff 的值，生成对应的移动指令 ('U', 'D', 'L', 'R')。特别地，当目标字符是 'z' 时，先进行列移动再进行行移动，以避免移动到字母板外。每完成一个字符的定位，就添加 '!' 操作以收集字符。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def alphabetBoardPath(self, target):
        board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]  # 字母板
        char_dict = {}  # 字符位置映射
        for i in range(len(board)):  # 构建映射表
            for j in range(len(board[i])):
                char_dict[board[i][j]] = (i, j)
        target = 'a' + target  # 从 'a' 开始
        res = []  # 结果指令集
        for i in range(1, len(target)):  # 遍历 target
            diff = [char_dict[target[i]][0] - char_dict[target[i - 1]][0], char_dict[target[i]][1] - char_dict[target[i - 1]][1]]  # 行列差
            if target[i] != 'z':  # 如果当前字符不是 'z'
                if diff[0] > 0:
                    res += diff[0] * ['D']  # 下移
                elif diff[0] < 0:
                    res += -diff[0] * ['U']  # 上移
                if diff[1] > 0:
                    res += diff[1] * ['R']  # 右移
                elif diff[1] < 0:
                    res += -diff[1] * ['L']  # 左移
            else:  # 特殊处理字符 'z'
                if diff[1] > 0:
                    res += diff[1] * ['R']
                elif diff[1] < 0:
                    res += -diff[1] * ['L']
                if diff[0] > 0:
                    res += diff[0] * ['D']
                elif diff[0] < 0:
                    res += -diff[0] * ['U']
            res.append('!')  # 收集字符
        return ''.join(res)

Explore

在字母板中，'z'是位于最后一行的唯一字符，处于第六行第一列。如果从其他字符移动到'z'，需要特别注意不要越界。标准的移动顺序（先行后列或先列后行）可能导致非法的步骤。例如，如果你从'w'（第五行第三列）直接向下移动到'z'，那么在正常的行移动后，尝试向右移动将会导致越出字母板边界。因此，将列移动放在前面是为了确保在达到第六行之前，已经调整到正确的列位置，从而避免越界问题。

字母板的设计中，某些行的长度不同。特别是从'e'（第一行第五列）到'f'（第二行第一列）的移动需要跨越行边界。在编写移动代码时，必须考虑这种行的变化。确保在执行列移动前已经完成了行移动，从而避免尝试访问不存在的列。具体来说，从'e'到'f'的移动会先向下（'D'），再处理任何必要的列移动。这种方法确保了即使在行长度不一的情况下，也可以安全地在字母板上导航。

在构建char_dict时，代码遍历了board中的每一行和每一列，为每个出现的字符创建了一个映射。这确保了所有在board上定义的字符都有正确的位置信息。如果board中缺少某个字符，那么这个字典将不会包含该字符的映射，如果尝试访问这样一个不存在的映射，代码将会抛出错误。在实际应用中，应确保board覆盖了所有可能需要的字符，或者在实现时增加错误处理逻辑，来处理字典查找失败的情况，例如通过抛出异常或返回特定的错误信息。