We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Alphabet Board Path

Difficulty: Medium

Problem Description

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0]. We may make moves in four directions: up ('U'), down ('D'), left ('L'), and right ('R'), as well as add the character at our current position to the answer with '!'. The goal is to return a sequence of moves that makes our answer equal to the target string in the minimum number of moves.

Key Insights

  • The board is structured as a grid with specific valid positions for letters.
  • Moves can only be made to adjacent valid positions.
  • The final move to add a character is represented by '!'.
  • The problem can be solved by calculating the optimal path from the current position to the target character's position.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the target string.
Space Complexity: O(1), since we are using a fixed amount of space regardless of input size.

Solution

To solve this problem, we will:

  1. Define the board as a 2D array where each character corresponds to its position.
  2. Maintain the current position on the board, starting at (0, 0).
  3. For each character in the target string, calculate the required moves to reach its position from the current position.
  4. Use directional moves ('U', 'D', 'L', 'R') to navigate to the target character's position.
  5. Append '!' to the result string once the character is reached.
  6. Update the current position after each character is added.

This approach ensures that we find the shortest path to each character in the target string.

Code Solutions

def alphabetBoardPath(target: str) -> str:
    board = [
        "abcde",
        "fghij",
        "klmno",
        "pqrst",
        "uvwxy",
        "z"
    ]
    position = (0, 0)  # Starting at (0, 0)
    result = []
    
    # Create a mapping of characters to their positions
    char_to_pos = {}
    for r in range(len(board)):
        for c in range(len(board[r])):
            char_to_pos[board[r][c]] = (r, c)
    
    for char in target:
        target_pos = char_to_pos[char]
        # Calculate row and column moves
        row_diff = target_pos[0] - position[0]
        col_diff = target_pos[1] - position[1]
        
        # Move down
        if row_diff > 0:
            result.append('D' * row_diff)
        # Move up
        if row_diff < 0:
            result.append('U' * (-row_diff))
        # Move right
        if col_diff > 0:
            result.append('R' * col_diff)
        # Move left
        if col_diff < 0:
            result.append('L' * (-col_diff))
        
        # Add the character
        result.append('!')
        # Update current position
        position = target_pos
    
    return ''.join(result)
← Back to All Questions