LeetCode 1138. Alphabet Board Path

Description

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 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.

Explanation

Move the position by rows and columns to the next character’s position. Note that there is only ‘z’ character on the last row.

Python Solution

``````class Solution:
def alphabetBoardPath(self, target: str) -> str:

board = [
['a', 'b', 'c', 'd', 'e'],
['f', 'g', 'h', 'i', 'j'],
['k', 'l', 'm', 'n', 'o'],
['p', 'q', 'r', 's', 't'],
['u', 'v', 'w', 'x', 'y'],
['z']
]

mapping = {}
for i in range(len(board)):
for j in range(len(board[i])):
mapping[board[i][j]] = [i, j]

result = ""

pos = [0, 0]

for c in target:
destination = mapping[c]

if pos[0] == mapping['z'][0] and pos[1] == mapping['z'][1] and destination[0] != mapping['z'][0] and destination[1] != mapping['z'][1]:
pos[0] -= 1
result += 'U'

if destination[1] - pos[1] > 0:
result += 'R' * (destination[1] - pos[1])
else:
result += 'L' * abs(destination[1] - pos[1])

if destination[0] - pos[0] > 0:
result += 'D' * (destination[0] - pos[0])
else:
result += 'U' * abs(destination[0] - pos[0])

result += '!'

pos[0] = destination[0]
pos[1] = destination[1]

return result``````
• Time Complexity: O(N).
• Space Complexity: O(N).