力扣---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 仅含有小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/alphabet-board-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

刚开始看到这道题，感觉挺简单，有辱中等难度之名。直到因为z的边界问题提交错误后才发现原来这玩意有边界。。。

代码如下，思路见注释

public class Solution {
    public String alphabetBoardPath(String target) {
        // 保存答案，用StringBuilder是为了省空间，参考javaString的特点。
        StringBuilder res = new StringBuilder();
        // 保存当前的坐标
        int[] coordinate = new int[2];
        // 储存需要移动的步数（移动后的坐标减去当前坐标）
        int[] tem;
        for (int i = 0; i < target.length(); i ++) {
            // 移动后的坐标和当前坐标相同时，原地不动，直接加!
            if (i > 0 && target.charAt(i) == target.charAt(i - 1)) {
                res.append('!');
            } else {
                // 移动后的坐标
                int[] temArr = findCoor(target.charAt(i));
                // 关于z的边界溢出判定，只有移动后的位置是z时会遇到这个问题。
                boolean juZ = temArr[0] == 5;
                // 存储需要移动的步数
                tem = new int[]{temArr[0] - coordinate[0], temArr[1] - coordinate[1]};
                // 给结果加答案。
                add(tem, res, juZ);
                // 更新当前位置
                coordinate = temArr;
            }
        }
        return res.toString();
    }
    // 计算移动后的坐标
    private int[] findCoor (char a) {
        int[] ans = new  int[2];
        // 由数学规律可知。
        ans[0] = (a - 'a') / 5;
        ans[1] = (a - 'a') % 5;
        return ans;
    }
    // 计算需要给答案添加的字符。由于StringBuilder是引用传递，所以直接用void即可。
    private void add(int[] arr, StringBuilder sb, boolean juZ) {
        // 垂直移动
        char vertical = arr[0] > 0 ? 'D' : 'U';
        arr[0] = Math.abs(arr[0]);
        // 水平移动
        char parallel = arr[1] > 0 ? 'R' : 'L';
        arr[1] = Math.abs(arr[1]);
        // z位置的边界溢出问题。
        if (juZ) {
            // 如果会溢出，则先向下走到边界
            add1(arr[0] - 1, vertical, sb);
            // 然后向左右移动
            add1(arr[1], parallel, sb);
            // 最后走到z
            add1(1, vertical, sb);
        } else {
            // 直接移动即可。
            add1(arr[0], vertical, sb);
            add1(arr[1], parallel, sb);
        }
        // 移动结束后别忘了加!
        sb.append('!');
    }
    private void add1(int num, char a, StringBuilder sb) {
        添加移动的步数
        sb.append(String.valueOf(a).repeat(num));
    }
}