题目链接

英文链接：https://leetcode.com/problems/alphabet-board-path/

中文链接：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：

1 2	输入：target = "leet" 输出："DDR!UURRR!!DDD!"

示例 2：

1 2	输入：target = "code" 输出："RR!DDRR!UUL!R!"

提示：

1 <= target.length <= 100
target 仅含有小写英文字母。

题目详解

根据题意，任意小写字母 c 的坐标为 ((c - 'a') / 5, (c - 'a') % 5)。
每次计算当前位置与下一个位置在两个方向的距离，并进行移动。
需要注意，z 是一个特殊的字符，为了保证正确移动，从任意字符移动到 z，要先左移、再下移的顺序；从 z 移动到任意字符，要先上移、再右移的顺序。综合起来，可以按照左下上右的顺序进行判断并移动。

public class LeetCode_01138 {

    public String alphabetBoardPath(String target) {
        StringBuilder sb = new StringBuilder();
        int x = 0, y = 0;
        for (char c : target.toCharArray()) {
            int dx = (c - 'a') / 5;
            int dy = (c - 'a') % 5;
            if (dy < y) {
                int n = y - dy;
                while (n-- > 0) {
                    sb.append('L');
                }
            }
            if (dx > x) {
                int n = dx - x;
                while (n-- > 0) {
                    sb.append('D');
                }
            }
            if (dx < x) {
                int n = x - dx;
                while (n-- > 0) {
                    sb.append('U');
                }
            }
            if (dy > y) {
                int n = dy - y;
                while (n-- > 0) {
                    sb.append('R');
                }
            }
            sb.append('!');
            x = dx;
            y = dy;
        }
        return sb.toString();
    }
}