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.

``````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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation