【每日一题Day116】LC1138字母板上的路径

【每日一题Day116】LC1138字母板上的路径 | 模拟

2023-12-27 25

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【每日一题Day116】LC1138字母板上的路径 | 模拟

字母板上的路径【LC1138】

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

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

如果方格存在，'U' 意味着将我们的位置上移一行；

如果方格存在，'D' 意味着将我们的位置下移一行；

如果方格存在，'L' 意味着将我们的位置左移一列；

如果方格存在，'R' 意味着将我们的位置右移一列；

'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。

（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

思路：直接模拟

每个字母位于字母版上的位置是[ i n d e x / 5 , i n d e x % 5 ] ，因此记录上一个位置，然后将其行移动至目标行、列移动至目标列即可，

特殊处理起点和终点在’z’的情况

实现

class Solution {
    public String alphabetBoardPath(String target) {
        int WIDTH = 5;
        StringBuilder res = new StringBuilder();
        int[] start = {0, 0};
        for (char c : target.toCharArray()){
            int[] end = new int[2];
            end[0] = (c -'a') / WIDTH;
            end[1] = (c -'a') % WIDTH;
            if (start[0] == 5){// 先向上
                while (end[0] < start[0]){
                    start[0]--;
                    res.append('U');
                }
            }
            if (end[0] == 5){//先向左
                 while (end[1] < start[1]){
                    start[1]--;
                    res.append('L');
                }
            }
            // 行 上下
            while (end[0] > start[0]){
                start[0]++;
                res.append('D');
            }
            while (end[0] < start[0]){
                start[0]--;
                res.append('U');
            }
            // 列 左右
            while (end[1] > start[1]){
                start[1]++;
                res.append('R');
            }
            while (end[1] < start[1]){
                start[1]--;
                res.append('L');
            }
            res.append('!');
        }
        return res.toString();
    }
}

复杂度

时间复杂度： O ( n × ( r + c ) ) ，其中 n 表示给定字符串的长度，r 表示字母板的行数， c 表示字母板的列数。

空间复杂度：O ( 1 ) 。除返回值以外不需要额外的申请空间。

优化：每次移动优先保证上移和左移

class Solution {
    public String alphabetBoardPath(String target) {
        int WIDTH = 5;
        StringBuilder res = new StringBuilder();
        int[] start = {0, 0};
        for (char c : target.toCharArray()){
            int[] end = new int[2];
            end[0] = (c -'a') / WIDTH;
            end[1] = (c -'a') % WIDTH;
            // 行 上
            while (end[0] < start[0]){
                start[0]--;
                res.append('U');
            }
             // 列 左
            while (end[1] < start[1]){
                start[1]--;
                res.append('L');
            }
            // 行 下
            while (end[0] > start[0]){
                start[0]++;
                res.append('D');
            }
            // 列 右
            while (end[1] > start[1]){
                start[1]++;
                res.append('R');
            }          
            res.append('!');
        }
        return res.toString();
    }
}

【每日一题Day116】LC1138字母板上的路径 | 模拟

字母板上的路径【LC1138】

热门文章

最新文章

相关电子书