Algorithm
Problem Name: 1138. Alphabet Board Path
Problem Link: https://leetcode.com/problems/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 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 <= 100targetconsists only of English lowercase letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const alphabetBoardPath = function(target) {
let sx = 0,
sy = 0;
let dir = "";
let a = "a".charCodeAt(0);
for (let c of target) {
let dx = (c.charCodeAt(0) - a) % 5,
dy = ((c.charCodeAt(0) - a) / 5) >> 0,
n;
if (sx > dx) {
n = sx - dx;
while (n--) dir += "L";
}
if (sy < dy) {
n = dy - sy;
while (n--) dir += "D";
}
if (sy > dy) {
n = sy - dy;
while (n--) dir += "U";
}
if (sx < dx) {
n = dx - sx;
while (n--) dir += "R";
}
dir += "!";
(sx = dx), (sy = dy);
}
return dir;
};
Input
target = "leet"
Output
"DDR!UURRR!!DDD!"
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def alphabetBoardPath(self, target: str) -> str:
ind = {s: [i // 5, i % 5] for i, s in enumerate(string.ascii_lowercase)}
x = y = 0
res = ""
for c in target:
xx, yy = ind[c]
if yy < y:
res += 'L' * (y - yy)
if xx > x:
res += 'D' * (xx - x)
if xx < x:
res += 'U' * (x - xx)
if yy > y:
res += 'R' * (yy - y)
res += '!'
x, y = xx, yy
return res
Input
target = "leet"
Output
"DDR!UURRR!!DDD!"