Leetcode - Alphabet Board Path Solution
1 min read

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

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×