# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1138.alphabet-board-path.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.