1138. Alphabet Board Path

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"], as shown in the diagram below.

We may make the following moves:

  • 'U' moves our position up one row, if the position exists on the board;
  • 'D' moves our position down one row, if the position exists on the board;
  • 'L' moves our position left one column, if the position exists on the board;
  • 'R' moves our position right one column, if the position exists on the board;
  • '!' adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

  • 1 <= target.length <= 100
  • target consists only of English lowercase letters.

这道题给了一个字母表盘,就是 26 个小写字母按每行五个排列,形成一个二维数组,共有六行,但第六行只有一个字母z。然后给了一个字符串 target,起始位置是在a,现在让分别按顺序走到 target 上的所有字符,问经过的最短路径是什么。这不禁让博主想到了智能电视系统 Ruko 连接 wiki 时输密码的操作,因为只能用遥控器,也是一个字母表盘,然后按方向键移动到想要输入的字母上,然后点击 OK,进行确认,再移动到下一个目标字符,跟这里完全是一样的操作。由于表盘上的字母位置是固定的,所以不需要进行遍历来找特定的字母,而是可以根据字母直接确定其在表盘的上的坐标,这样当前字母和目标字母的坐标都确定了,就可以直接找路径了,其实就是个曼哈顿距离。由于路径有很多条,只要保证距离最短都对,那么就可以先走横坐标,或先走纵坐标。其实这里选方向挺重要,因为有个很 tricky 的情况,就是字母z,因为最后一行只有一个字母z,其不能往右走,只能往上走,所以这里定一个规则,就是先往上走,再向右走。同理,从别的字母到z的话,也应该先往左走到头,再往下走。顺序确定好了,就可以想怎么正确的生成路径,往上的走的话,说明目标点在上方,则说明当前的x坐标大,则用 curX - x,由于不一定需要向上走,所以这个差值有可能是负数,则需要跟0比较大小,取较大的那个。其他情况,都是同理的,往右走用目标y坐标减去当前y坐标;往左走,用当前y坐标减去目标y坐标;往下走,用目标x坐标减去当前x坐标,最后再加上感叹号。结束一轮后,别忘了更新 curX 和 curY,参见代码如下:

class Solution {
public:
    string alphabetBoardPath(string target) {
        string res;
        int curX = 0, curY = 0;
        for (char c : target) {
            int x = (c - 'a') / 5, y = (c - 'a') % 5;
            res += string(max(0, curX - x), 'U') + string(max(0, y - curY), 'R') + string(max(0, curY - y), 'L') + string(max(0, x - curX), 'D') + '!';
            curX = x;
            curY = y;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1138

参考资料:

https://leetcode.com/problems/alphabet-board-path/

https://leetcode.com/problems/alphabet-board-path/discuss/345278/C%2B%2BJava-O(n)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation