文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：字母板上的路径

出处：1138. 字母板上的路径

难度

4 级

题目描述

要求

我们从一块字母板上的位置 (0,0)\texttt{(0, 0)}(0, 0) 出发，该坐标对应的字符为 board[0][0]\texttt{board[0][0]}board[0][0]。

在本题中，字母板为 board=["abcde","fghij","klmno","pqrst","uvwxy","z"]\texttt{board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]}board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

• 如果方格存在，‘U’\texttt{`U'}‘U’ 意味着将我们的位置上移一行；
• 如果方格存在，‘D’\texttt{`D'}‘D’ 意味着将我们的位置下移一行；
• 如果方格存在，‘L’\texttt{`L'}‘L’ 意味着将我们的位置左移一列；
• 如果方格存在，‘R’\texttt{`R'}‘R’ 意味着将我们的位置右移一列；
• ‘!’\texttt{`!'}‘!’ 会把在我们当前位置 (r,c)\texttt{(r, c)}(r, c) 的字符 board[r][c]\texttt{board[r][c]}board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target\texttt{target}target 相同。你可以返回任何达成目标的路径。

示例

示例 1：

输入：target="leet"\texttt{target = "leet"}target = "leet"
输出："DDR!UURRR!!DDD!"\texttt{"DDR!UURRR!!DDD!"}"DDR!UURRR!!DDD!"

示例 2：

输入：target="code"\texttt{target = "code"}target = "code"
输出："RR!DDRR!UUL!R!"\texttt{"RR!DDRR!UUL!R!"}"RR!DDRR!UUL!R!"

数据范围

• 1≤target.length≤100\texttt{1} \le \texttt{target.length} \le \texttt{100}1≤target.length≤100
• target\texttt{target}target 仅含有小写英语字母

解法

思路和算法

字母 ‘a’\text{`a'}‘a’ 到 ‘z’\text{`z'}‘z’ 可以分别对应整数 000 到 252525，根据整数值即可得到每个字母对应字母板上的位置。

有两种做法可以得到每个字母对应字母板上的位置。第一种做法是使用哈希表记录每个字母对应字母板上的位置，第二种做法是不用哈希表，而是根据字母对应的整数计算字母对应字母板上的位置。两种做法得到每个字母对应字母板上的位置的时间复杂度相同，第二种做法可以省去哈希表的空间。此处的解法使用第二种做法。

用 index\textit{index}index 表示字母对应的整数，则有 0≤index≤250 \le \textit{index} \le 250≤index≤25。由于字母板有 555 列，因此 index\textit{index}index 所在行是 ⌊index5⌋\Big\lfloor\dfrac{\textit{index}}{5}\Big\rfloor⌊5index​⌋，index\textit{index}index 所在列是 indexmod5\textit{index} \bmod 5indexmod5。

为了得到最短的指令序列，对于目标 target\textit{target}target 中的每个字母，需要在字母板上按照最短路径移动到该字母所在位置，然后使用指令 ‘!’\text{`!'}‘!’ 将字母添加到答案中。按照最短路径移动时，首先根据原位置和新位置得到移动方向和移动次数，然后从原位置开始，在水平方向和竖直方向上分别向新位置移动。如果原位置和新位置相同则不需要移动。

初始位置是 (0,0)(0, 0)(0,0)。每次移动到新位置之后，需要将原位置的值更新为新位置的值，后续移动时根据更新后的原位置的值决定移动方向和移动次数。

由于字母 ‘z’\text{`z'}‘z’ 单独出现在最后一行，因此不能从字母 ‘z’\text{`z'}‘z’ 向右移动，也不可能通过向左移动到达字母 ‘z’\text{`z'}‘z’，否则将导致移动到不合法的位置（即没有字母的位置）。为了避免在包含字母 ‘z’\text{`z'}‘z’ 的情况下移动到不合法的位置，如果移动方向是左下或右上，则需要规定移动顺序：

• 如果移动方向是左下，必须先向左移动，后向下移动；

• 如果移动方向是右上，必须先向上移动，后向右移动。

对于其余的移动方向，包括上、下、左、右、左上和右下，则不需要规定移动顺序，先在水平方向移动或者先在竖直方向移动都是可以的。

代码

class Solution {public String alphabetBoardPath(String target) {StringBuffer sb = new StringBuffer();int row = 0, column = 0;int length = target.length();for (int i = 0; i < length; i++) {char c = target.charAt(i);int index = c - 'a';int newRow = index / 5, newColumn = index % 5;int rowDifference = newRow - row, columnDifference = newColumn - column;if (rowDifference > 0 && columnDifference < 0) {for (int j = 0; j > columnDifference; j--) {sb.append('L');}for (int j = 0; j < rowDifference; j++) {sb.append('D');}} else if (rowDifference < 0 && columnDifference > 0) {for (int j = 0; j > rowDifference; j--) {sb.append('U');}for (int j = 0; j < columnDifference; j++) {sb.append('R');}} else {if (rowDifference < 0) {for (int j = 0; j > rowDifference; j--) {sb.append('U');}} else if (rowDifference > 0) {for (int j = 0; j < rowDifference; j++) {sb.append('D');}}if (columnDifference < 0) {for (int j = 0; j > columnDifference; j--) {sb.append('L');}} else if (columnDifference > 0) {for (int j = 0; j < columnDifference; j++) {sb.append('R');}}}sb.append('!');row = newRow;column = newColumn;}return sb.toString();}
}

复杂度分析

• 时间复杂度：O(n)O(n)O(n)，其中 nnn 是字符串 target\textit{target}target 的长度。需要遍历字符串 target\textit{target}target 一次，对于每个字母生成指令序列，由于每个字母的指令最多为 101010 次，包括最多需要在字母板上移动 999 次和 111 次 ‘!’\text{`!'}‘!’，因此时间复杂度是 O(n)O(n)O(n)。

• 空间复杂度：O(n)O(n)O(n)，其中 nnn 是字符串 target\textit{target}target 的长度。空间复杂度主要取决于结果字符串的空间，由于每个字母的指令最多为 101010 次，包括最多需要在字母板上移动 999 次和 111 次 ‘!’\text{`!'}‘!’，因此空间复杂度是 O(n)O(n)O(n)。由于 Java 中的 String\texttt{String}String 类型的对象不可变，因此结果字符串的 O(n)O(n)O(n) 空间不可省略。