Leetcode - Alphabet Board Path Solution

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 in Python

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        _curr_ = "a"
        moves = ""
        for _next_ in target:
            col_pos_curr, row_pos_curr = divmod((ord(_curr_)-97),5) 
            col_pos_next, row_pos_next = divmod((ord(_next_)-97),5) 
            col_diff = abs(col_pos_next-col_pos_curr)
            row_diff = abs(row_pos_next-row_pos_curr)
            if _curr_ == "z":
                moves += "U"*col_diff if col_pos_curr > col_pos_next else "D"*col_diff
                moves += "L"*row_diff if row_pos_curr > row_pos_next else "R"*row_diff
            else:
                moves += "L"*row_diff if row_pos_curr > row_pos_next else "R"*row_diff
                moves += "U"*col_diff if col_pos_curr > col_pos_next else "D"*col_diff
            moves += "!"
            _curr_ = _next_
        return moves