# 1138. 字母板上的路径
### 题目地址(1138. 字母板上的路径)
### 题目描述
```
我们从一块字母板上的位置 (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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
