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

思路

解题思路

因为字母是有限的且位置固定的，我们可以映射一下每个字母的位置，例如，把a映射为(0,0)，b映射为(0,1),f映射为(1,0)。

可以把初始位置current设置为(0,0)，然后遍历target的每一个点，计算每个点的位置next，计算current到next的路径，并将答案append到结果中，然后更新current。

数据结构选择

本题中的计算基本是单纯模拟，所以可以采用一个StingBuilder进行答案存储，采用一个一维数组保存当前坐标。

题解

class Solution {
    //a={0,0},f={1,0}
    public String alphabetBoardPath(String target) {
        int[] current={0,0};
        int n=target.length();
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<n;i++){
            int t=target.charAt(i)-'a';
            if(current[0]==5 && current[1]==0){
                if(t==25){
                    sb.append("!");
                    continue;
                }
                else{
                    sb.append("U");
                    current[0]=4;
                }
            }
            boolean zfalg=false;
            if(t==25){
                zfalg=true;
                t=20;
            }
            int x=t/5,y=t%5;
            if(x>current[0]){
                for(int num=0;num<x-current[0];num++){
                    sb.append("D");
                }
            }
            else{
                for(int num=0;num<current[0]-x;num++){
                    sb.append("U");
                }
            }
            if(y>current[1]){
                for(int num=0;num<y-current[1];num++){
                    sb.append("R");
                }
            }
            else{
                for(int num=0;num<current[1]-y;num++){
                    sb.append("L");
                }
            }
            if(zfalg){
                sb.append("D!");
                current[0]=5;
                current[1]=0;
            }
            else{
                sb.append("!");
                current[0]=x;
                current[1]=y;
            }
        }
        return sb.toString();
    }
}