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 characterboard[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.
Related Topics:
Hash Table, String
// OJ: https://leetcode.com/problems/alphabet-board-path/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
string alphabetBoardPath(string target) {
int x = 0, y = 0;
string ans;
for (char c : target) {
int p = (c - 'a') / 5, q = (c - 'a') % 5;
while (x != p || y != q) {
if (q >= y) {
if (p > x) {
++x;
ans += 'D';
} else if (p < x) {
--x;
ans += 'U';
} else {
++y;
ans += 'R';
}
} else {
--y;
ans += 'L';
}
}
ans += '!';
}
return ans;
}
};