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.
// 4ms, 62%
class Solution {
pair<int,int> getPos(char c) {
auto a = c - 'a';
return {a / 5, a % 5};
}
string move(int dx, int dy, bool xFirst) {
string sx, sy;
if (dx != 0) {
auto out = dx > 0? 'D' : 'U';
sx = string(abs(dx), out);
}
if (dy != 0) {
auto out = dy > 0? 'R' : 'L';
sy = string(abs(dy), out);
}
if (xFirst) return sx + sy;
else return sy + sx;
}
public:
string alphabetBoardPath(string target) {
string res;
auto cur = make_pair(0, 0);
for (const auto& c : target) {
auto pos = getPos(c);
auto dx = pos.first - cur.first;
auto dy = pos.second - cur.second;
bool xFirst = cur.first == 5;
res += move(dx, dy, xFirst);
cur = pos;
res += '!';
}
return res;
}
};