Skip to content

1138. Alphabet Board Path

Difficulty Topics

Description

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.

Solution

alphabet-board-path.py
class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        res, i, j = "", 0, 0

        for t in target:
            v = ord(t) - ord('a')
            ti, tj = v // 5, v % 5

            if ti == i and tj == j:
                res += "!"
            else:
                if ti != i:
                    if ti >= i:
                        if ti == 5 and j != 0:
                            res += "D" * (ti - i - 1)
                        else:
                            res += "D" * (ti - i)
                    else:
                        res += "U" * (i - ti)

                if tj != j:
                    if tj >= j:
                        res += "R" * (tj - j)
                    else:
                        res += "L" * (j - tj)

                    if ti == 5:
                        res += "D"

                res += "!"

            i, j = ti, tj

        return res