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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Alphabet Board Path

Number: 1238

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an alphabet board where each cell contains a letter (with "z" at board position (5, 0) and all other rows fully filled from "a" to "y"), start from position (0, 0) and generate a sequence of moves to spell a given target string. The allowed moves are: U (up), D (down), L (left), R (right), and "!" to pick the letter at the current position. The goal is to return a valid sequence of moves that builds the target string in the minimum number of moves.

Key Insights

  • Determine the row and column for each letter (using integer division and modulus).
  • Because "z" is in a special row that only contains one column, the move order is critical to avoid invalid positions.
  • For target letter "z", perform horizontal moves before vertical moves; for all other letters, do vertical moves before horizontal moves.
  • Build the answer step-by-step by moving from your current position to each target letter.

Space and Time Complexity

Time Complexity: O(N) where N is the length of target (each move is processed in constant time) Space Complexity: O(N) for the resulting string of moves

Solution

The approach calculates the destination coordinates for each character. For each letter in the target:

  1. Convert the letter to its board coordinates (row and col). For example, for letter c, row = (ord(c) - ord('a')) // 5 and col = (ord(c) - ord('a')) % 5. Note that "z" (the 26th letter) always maps to (5, 0).
  2. To move from the current position (curRow, curCol) to the target's (targetRow, targetCol), decide on the order of moves:
    • If the target letter is "z", first move horizontally (left or right) then vertically (up or down) to avoid stepping into invalid regions from the extra row.
    • For any other letter, move vertically (up or down) first, then horizontally (left or right).
  3. Append "!" to the moves after reaching each letter.
  4. Update the current position to the letter's coordinates.

This method ensures you only traverse valid cells on the board and minimizes moves by taking the optimal coordinate difference each step.

Code Solutions

# Python solution with clear variable names and inline comments.
class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        # Starting position at the top-left corner (0,0)
        current_row, current_col = 0, 0
        result = []
        
        # Helper function to convert letter to its (row, col) coordinates
        def getPosition(letter):
            index = ord(letter) - ord('a')
            return index // 5, index % 5
        
        for char in target:
            target_row, target_col = getPosition(char)
            # If target character is 'z', move horizontally first then vertically
            if char == 'z':
                # Move left if needed
                while current_col > target_col:
                    result.append("L")
                    current_col -= 1
                # Move right if needed
                while current_col < target_col:
                    result.append("R")
                    current_col += 1
                # Then move down if needed
                while current_row < target_row:
                    result.append("D")
                    current_row += 1
                # Then move up if needed
                while current_row > target_row:
                    result.append("U")
                    current_row -= 1
            else:
                # For all other characters, move vertically first
                while current_row > target_row:
                    result.append("U")
                    current_row -= 1
                while current_row < target_row:
                    result.append("D")
                    current_row += 1
                # Then move horizontally
                while current_col > target_col:
                    result.append("L")
                    current_col -= 1
                while current_col < target_col:
                    result.append("R")
                    current_col += 1
            # Append pick-up action for the letter
            result.append("!")
        return "".join(result)
← Back to All Questions