Skip to content

Latest commit

 

History

History
119 lines (75 loc) · 3.85 KB

1138.alphabet-board-path.md

File metadata and controls

119 lines (75 loc) · 3.85 KB

题目地址(1138. 字母板上的路径)

https://leetcode-cn.com/problems/alphabet-board-path/

题目描述

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

前置知识

  • 矩阵

公司

  • 暂无

思路

首先我们需要明确三点:

  1. 题目中的字母板 board 是确认的,即题目给出的 board。如果题目的 board 是动态的,参数给出的,那么难度会加大。
  2. 对于 target。我们需要先录入 target 第一个字母,类似 xxxx! 的序列。然后是第二个字母 。。。而不能以其他顺序录入,否则难度也会加大。
  3. 如果当前的位置是 (x,y), 当前需要录入的字母位于 board 的 (tx, ty)。 那么有如下最短路径可能:
    • 先右再下或者先下后右,前提是 (tx, ty) 在 (x,y)右下。
    • 先左再下或者先下后左,前提是 (tx, ty) 在 (x,y)左下。
    • 先右再上或者先上后右,前提是 (tx, ty) 在 (x,y)右上。
    • 先左再上或者先上后左,前提是 (tx, ty) 在 (x,y)左上。

由于题目要求返回任意满足题意的路径,因此我们无论采用哪种都可以。

关键点

  • 理解题意
  • 矩阵坐标映射

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        board = []
        for i in range(5):
            for j in range(5):
                board.append((i,j))
        board.append((5,0))
        last_x = last_y = 0
        ans = ''
        for c in target:
            nxt_x, nxt_y = board[ord(c)-ord('a')]
            up = max(0, last_x - nxt_x)
            down = max(0, nxt_x - last_x)
            left = max(0, last_y - nxt_y)
            right = max(0, nxt_y - last_y)
            ans += 'U'*up + 'L'*left + 'D'*down + 'R'*right + '!'
            last_x, last_y = nxt_x, nxt_y
        return ans

复杂度分析

令 n 为 target 长度。

  • 时间复杂度:构建 board 需要常数的时间,遍历 target 需要 n 的时间,因此时间复杂度为 $O(n)$
  • 空间复杂度:board 长度为固定的 26,因此空间复杂度为 $O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。