跳到主要内容

1138.字母板上的路径

· 阅读需 3 分钟

1、题干​

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

2、思路​

根据题意模拟，关键注意 z 的路线否则会越界；任意字母到 z 的路线优先在水平方向移动，其他情况则优先在垂直方向移动

3、代码​

function alphabetBoardPath(target: string): string {
    let ans = '', p1 = [0, 0], p2 = [0, 0];

    for (let i = 0; i < target.length; i++) {
        p1 = p2;
        const code = target.charCodeAt(i) - 97;
        p2 = [code / 5 >> 0, code % 5];

        const dx = p2[1] - p1[1], dy = p2[0] - p1[0];
        const my = (dy >= 0 ? 'D'.repeat(dy) : 'U'.repeat(-dy));
        const mx = (dx >= 0 ? 'R'.repeat(dx) : 'L'.repeat(-dx));

        ans += (target[i] === 'z' ? mx + my : my + mx) + '!';
    }

    return ans;
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png