[leetcode每日一题]2.12

​​1138. 字母板上的路径​​

难度中等79

我们从一块字母板上的位置 ​​(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​​ 仅含有小写英文字母。

Solution

一语道破，虽然我也想出来了。上移的时候优先上，再左右，下移的时候优先左右，再下。

class Solution {
public:
    string alphabetBoardPath(string target) {
        char cur = 'a';
        string res = "";
        int stx = 0;
        int sty = 0;
        int fix = 0;
        int fiy = 0;
        int isdown = 0;
        int isright = 0;
        char element[] = {'L', 'R'};
        for(auto& ch:target){
            fix = int(ch-'a')%5;
            fiy = int(ch-'a')/5;
            // 因为z的特殊性，所以在上方要先向上走，在下方要先左右走
            // 用2个bit表示
            // 上0下1， 左0右1
            isdown = fiy <= sty ? 0 : 1;
            isright = fix <= stx ? 0 : 1;
            if(isdown){
                for(int i=0;i<abs(fix - stx);i++){
                    res += element[isright];
                }
                for(int i=0;i<abs(fiy - sty);i++){
                    res += 'D';
                }
            }
            else{
                for(int i=0;i<abs(fiy - sty);i++){
                    res += 'U';
                }
                for(int i=0;i<abs(fix - stx);i++){
                    res += element[isright];
                }
            }
            res += '!';
            stx = fix;
            sty = fiy;
        }
        return res;
    }
};

不过官方题解还是给我上了一课。既然如此，那我只需要考虑排布次序即可。即，依次判断怎么走，先向上，再向左，再向下向右/向右向下。

另外学习使用append这个api，什么时候C++这么python化了。

class Solution {
public:
    string alphabetBoardPath(string target) {
        int cx = 0, cy = 0;
        string res;
        for (char c : target) {
            int nx = (c - 'a') / 5;
            int ny = (c - 'a') % 5;
            if (nx < cx) {
                res.append(cx - nx, 'U');
            }
            if (ny < cy) {
                res.append(cy - ny, 'L');
            } 
            if (nx > cx) {
                res.append(nx - cx, 'D');
            }
            if (ny > cy) {
                res.append(ny - cy, 'R');
            }  
            res.push_back('!');
            cx = nx;
            cy = ny;
        }
        return res;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/alphabet-board-path/solution/zi-mu-ban-shang-de-lu-jing-by-leetcode-s-c30t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。