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

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 == mapping['z'] and pos == mapping['z'] and destination != mapping['z'] and destination != mapping['z']:
pos -= 1
result += 'U'

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

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

result += '!'

pos = destination
pos = destination

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