当前位置：首页 > news >正文

字母板上的路径题解，力扣官方出来挨打（小声）

news 2025/7/13 1:14:24

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

在本题里，字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]，如下所示。
我们可以按下面的指令规则行动：
如果方格存在，‘U’ 意味着将我们的位置上移一行；
如果方格存在，‘D’ 意味着将我们的位置下移一行；
如果方格存在，‘L’ 意味着将我们的位置左移一列；
如果方格存在，‘R’ 意味着将我们的位置右移一列；
‘!’ 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
（注意，字母板上只存在有字母的位置。）
返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

这道题在拿到的时候第一眼我想的是把所有字母到另一字母的路径全部通过遍历出来，然后存在一张map里，在通过Map拿，然后拼到答案里，但是这样的开销有些大，因为要做图搜索，且要遍历26*25次，所以图搜索的思路先放弃，绝对不是图搜索学得不好不会写什么的（世上无难事，只要肯放弃）_(:з」∠)_

那么就换个思路，开始找规律吧（早干啥了啊喂）。（╬￣皿￣）＝○＃（￣＃）３￣）

我们可以发现上面的图就是一个二维数组。以ai为例，a的坐标是[0,0]，i的坐标是[1,4]，alphabetBoardPath(“i”)=“URRRR!”
也就是说纵向移动，或者说是U和D在答案中的数量取决于ax-ix，横向移动，或者说是U和D在答案中的数量取决于ay-iy。
将a在26个英文字母中的顺序视为0，字母在图表中的x = 他在26个英文字母中的顺序/5（向下取整），y = 他在26个英文字母中的顺序%5。例如z，在字母中的顺序为25，x=25/5=5，y=25%5=0，z的坐标为[5,0]。（心机之蛙一直摸你肚子）
我们将规律转化一下可得一下代码：

    public String alphabetBoardPath(String target) {StringBuilder result = new StringBuilder();target = "a" + target;for (int i = 0; i < target.length() - 1; i++) {result.append(returnOperation((Integer) (target.charAt(i) - 'a'), (Integer) (target.charAt(i + 1) - 'a')));}return result.toString();}String returnOperation(int strat, int end) {StringBuilder result = new StringBuilder();int lateralMovement = strat % 5 - end % 5;int longitudinalMovement = strat / 5 - end / 5;for (int i = 0; i < Math.abs(longitudinalMovement); i++) {result.append(longitudinalMovement < 0 ? "D" : "U");}for (int i = 0; i < Math.abs(lateralMovement); i++) {result.append(lateralMovement < 0 ? "R" : "L");}result.append("!");return result.toString();}

然鹅，力扣竟然报错了：
在这里插入图片描述
输出：
“DDDDD!UUUUURRR!DDDDDLLL!”
预期结果：
“DDDDD!UUUUURRR!DDDDLLLD!”
我实在是百思不得其解，无论如何都看不出来我为啥错了。(￢‸￢) ?
于是去看了力扣官方给的答案：

    public String alphabetBoardPath(String target) {int cx = 0, cy = 0;StringBuilder res = new StringBuilder();for (int i = 0; i < target.length(); i++) {char c = target.charAt(i);int nx = (c - 'a') / 5;int ny = (c - 'a') % 5;if (nx < cx) {for (int j = 0; j < cx - nx; j++) {res.append('U');}}if (ny < cy) {for (int j = 0; j < cy - ny; j++) {res.append('L');}} if (nx > cx) {for (int j = 0; j < nx - cx; j++) {res.append('D');}}if (ny > cy) {for (int j = 0; j < ny - cy; j++) {res.append('R');}}  res.append('!');cx = nx;cy = ny;}return res.toString();}作者：LeetCode-Solution
链接：https://leetcode.cn/problems/alphabet-board-path/solution/zi-mu-ban-shang-de-lu-jing-by-leetcode-s-c30t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

（╯’ - ‘)╯︵ ┻━┻
我猜了一下应该是因为路径的顺序，先赌他一手，按照ULDR的顺序返回。先把桌子摆好┬─┬ ノ(’-'ノ)
改出了以下代码：

    public String alphabetBoardPath(String target) {StringBuilder result = new StringBuilder();target = "a" + target;for (int i = 0; i < target.length() - 1; i++) {result.append(returnOperation((Integer) (target.charAt(i) - 'a'), (Integer) (target.charAt(i + 1) - 'a')));}return result.toString();}String returnOperation(int strat, int end) {StringBuilder result = new StringBuilder();int lateralMovement = strat % 5 - end % 5;int longitudinalMovement = strat / 5 - end / 5;for (int i = 0; i < longitudinalMovement; i++) {result.append("U");}for (int i = 0; i < lateralMovement; i++) {result.append("L");}for (int i = 0; i > longitudinalMovement; i--) {result.append("D");}for (int i = 0; i > lateralMovement; i--) {result.append("R");}result.append("!");return result.toString();}