{x}
blog image

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.

Solution Explanation: Alphabet Board Path

This problem involves finding the shortest sequence of moves to spell a target word on an alphabet board. The board is a 6x5 grid where each cell contains a letter, and the starting position is (0,0) representing 'a'. The allowed moves are 'U' (up), 'D' (down), 'L' (left), 'R' (right), and '!' (select the current cell's letter).

Approach: Simulation

The most straightforward approach is to simulate the movement on the board character by character. For each character in the target string:

  1. Calculate target coordinates: Determine the row (x) and column (y) coordinates of the target character on the board. The letter 'z' is a special case as it is alone in its row.

  2. Move to target: We need to move from the current position to the target position. The order of movements matters to ensure we don't get stuck. Generally, we prioritize upward and leftward movements to avoid getting blocked by the 'z' position. Therefore, we first move upwards ('U') as many times as needed, then move leftward ('L'), then downward ('D'), and finally rightward ('R').

  3. Append to result: After reaching the target, we append '!' to the result string to select the current character.

  4. Update current position: Update the current position (i, j) to the target coordinates.

This process is repeated for each character in the target string.

Time and Space Complexity Analysis

  • Time Complexity: The algorithm iterates through each character of the target string once. The number of movements to reach each target character is at most the size of the board (O(1)). Therefore, the overall time complexity is O(n), where n is the length of the target string.

  • Space Complexity: The space used is dominated by the result string, whose length is proportional to the length of the target string plus the number of movements. Therefore, the space complexity is O(n) in the worst case. We use a constant amount of extra space for variables, which is O(1).

Code Implementation (Python)

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        i = j = 0
        ans = []
        for c in target:
            v = ord(c) - ord("a")
            x, y = v // 5, v % 5
            while j > y:
                j -= 1
                ans.append("L")
            while i > x:
                i -= 1
                ans.append("U")
            while j < y:
                j += 1
                ans.append("R")
            while i < x:
                i += 1
                ans.append("D")
            ans.append("!")
        return "".join(ans)

The Python code directly implements the simulation approach. Other languages (Java, C++, Go) follow a similar structure, differing only in syntax and data structures. All versions have the same time and space complexities.