LeetCode 1138 - Alphabet Board Path

The problem gives us a special alphabet board and asks us to generate the shortest sequence of moves needed to spell a target string. The board contains lowercase English letters arranged in rows: We always begin at position (0, 0), which corresponds to the character 'a'.

leetcodemediumhash-tablestring

LeetCode Problem 1138

Difficulty: 🟡 Medium
Topics: Hash Table, String

Solution

Problem Understanding

The problem gives us a special alphabet board and asks us to generate the shortest sequence of moves needed to spell a target string. The board contains lowercase English letters arranged in rows:

abcde
fghij
klmno
pqrst
uvwxy
z

We always begin at position (0, 0), which corresponds to the character 'a'. From any valid position on the board, we can move:

  • Up with 'U'
  • Down with 'D'
  • Left with 'L'
  • Right with 'R'

After reaching a desired character, we append '!' to indicate selecting that character.

The goal is to produce a movement sequence that spells the given target string using the minimum number of moves.

The input consists of a string target, containing only lowercase English letters. The output is a string representing the movement instructions and selection operations required to spell the target.

The constraints are relatively small:

  • 1 <= target.length <= 100
  • Only lowercase English letters are used.

Since there are only 26 possible letters and the target length is at most 100, efficiency is not a major concern. However, correctness is tricky because the board is irregular. Every row except the last has five columns, but the last row contains only 'z'.

This irregular shape introduces an important edge case. The character 'z' sits alone at (5, 0), meaning positions like (5, 1) or (5, 2) do not exist. A naive movement strategy can accidentally try to move into invalid cells.

For example:

  • Moving to 'z' requires caution because we must avoid stepping into non existent cells.
  • Moving from 'z' also requires care, since we should move upward before moving right.
  • Consecutive repeated characters should still append '!' without unnecessary movement.

The problem guarantees that all target characters are valid lowercase letters, so we never need to handle invalid input.

Approaches

Brute Force Approach

A brute force solution would treat the board as a graph and use a shortest path algorithm, such as Breadth First Search (BFS), for every character transition.

For each target character:

  1. Start from the current position.
  2. Run BFS to find the shortest path to the next character.
  3. Record the movement sequence.
  4. Append '!'.

Since the board contains only 26 cells, BFS would always be fast in practice. Each transition would search through all reachable cells until the destination is found.

This approach is correct because BFS guarantees the shortest path in an unweighted graph. However, it is unnecessarily complicated. The board structure is fixed and extremely small, meaning we can directly compute the movement between positions without graph traversal.

Optimal Approach

The key observation is that every character has a fixed coordinate on the board. Since movement cost is simply Manhattan movement, we can directly calculate how to move between two coordinates.

For each target character:

  1. Determine its board coordinates.
  2. Compute row and column differences from the current position.
  3. Generate movement instructions directly.

The important insight is handling 'z' safely.

Because 'z' is the only character in row 5, we must prioritize movement order:

  • Move up before right when leaving 'z'
  • Move left before down when entering 'z'

A reliable strategy is:

  1. Move Up
  2. Move Left
  3. Move Down
  4. Move Right

This ordering guarantees we never enter invalid cells.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × 26) O(26) Run BFS for every character transition
Optimal O(n) O(1) Direct coordinate movement with careful ordering

Here, n is the length of target.

Algorithm Walkthrough

Optimal Algorithm

  1. Create a mapping from every letter to its (row, column) coordinate on the board.

Since the alphabet layout is fixed, we can compute coordinates mathematically. For a character c:

  • index = ord(c) - ord('a')
  • row = index // 5
  • col = index % 5

This gives instant access to every letter's position. 2. Start at the position of 'a', which is (0, 0).

We maintain the current cursor position as (current_row, current_col). 3. Process each character in target.

For each target character, retrieve its destination coordinates. 4. Move vertically upward first.

If the destination row is smaller than the current row, append 'U' repeatedly.

This is especially important when moving away from 'z'. 5. Move horizontally left second.

If the destination column is smaller, append 'L'.

This prevents accidentally stepping into invalid cells when targeting 'z'. 6. Move vertically downward third.

If the destination row is larger, append 'D'. 7. Move horizontally right last.

If the destination column is larger, append 'R'. 8. Append '!' after reaching the character.

This records selecting the letter. 9. Update the current position.

After selecting the character, make it the new starting point for the next transition.

Why it works

The algorithm always produces a valid shortest path because every move directly decreases the Manhattan distance to the target coordinate. Since no unnecessary movement occurs, the path length is minimal.

The movement order ensures correctness for 'z'. By moving upward and left before downward and right, we never attempt to step into non existent cells in the final row. This invariant guarantees all intermediate positions are valid.

Python Solution

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        result: list[str] = []

        current_row, current_col = 0, 0

        for char in target:
            index = ord(char) - ord('a')
            target_row = index // 5
            target_col = index % 5

            # Move up first
            while current_row > target_row:
                result.append('U')
                current_row -= 1

            # Move left second
            while current_col > target_col:
                result.append('L')
                current_col -= 1

            # Move down third
            while current_row < target_row:
                result.append('D')
                current_row += 1

            # Move right last
            while current_col < target_col:
                result.append('R')
                current_col += 1

            result.append('!')

        return ''.join(result)

The implementation follows the algorithm exactly. We maintain the current cursor position and compute the target position for each character mathematically.

Instead of storing the board explicitly, we exploit the predictable layout of the alphabet. Since letters are ordered sequentially, integer division and modulo provide the coordinates immediately.

The order of movement is the most important implementation detail. We always process:

  1. Up
  2. Left
  3. Down
  4. Right

This guarantees safe navigation around 'z'.

The result is built using a list of characters and joined at the end. This is preferable to repeated string concatenation because Python strings are immutable, and repeated concatenation would create unnecessary intermediate strings.

Go Solution

func alphabetBoardPath(target string) string {
	var result []byte

	currentRow, currentCol := 0, 0

	for _, ch := range target {
		index := int(ch - 'a')
		targetRow := index / 5
		targetCol := index % 5

		// Move up first
		for currentRow > targetRow {
			result = append(result, 'U')
			currentRow--
		}

		// Move left second
		for currentCol > targetCol {
			result = append(result, 'L')
			currentCol--
		}

		// Move down third
		for currentRow < targetRow {
			result = append(result, 'D')
			currentRow++
		}

		// Move right last
		for currentCol < targetCol {
			result = append(result, 'R')
			currentCol++
		}

		result = append(result, '!')
	}

	return string(result)
}

The Go implementation mirrors the Python logic closely.

One difference is that Go uses a []byte slice for efficient string construction. Since strings are immutable in Go, repeatedly concatenating strings would be inefficient. Appending bytes and converting once at the end is the idiomatic approach.

Go also uses rune iteration with for _, ch := range target, ensuring character handling is safe even though only lowercase English letters are present.

No special overflow handling is necessary because coordinates remain extremely small.

Worked Examples

Example 1

Input:

target = "leet"
Step Character Current Position Target Position Moves Result So Far
1 l (0,0) (2,1) DDR DDR!
2 e (2,1) (0,4) UURRR DDR!UURRR!
3 e (0,4) (0,4) none DDR!UURRR!!
4 t (0,4) (3,4) DDD DDR!UURRR!!DDD!

Final output:

"DDR!UURRR!!DDD!"

Example 2

Input:

target = "code"
Step Character Current Position Target Position Moves Result So Far
1 c (0,0) (0,2) RR RR!
2 o (0,2) (2,4) DDRR RR!DDRR!
3 d (2,4) (0,3) UUL RR!DDRR!UUL!
4 e (0,3) (0,4) R RR!DDRR!UUL!R!

Final output:

"RR!DDRR!UUL!R!"

Example: Moving To and From 'z'

Consider:

target = "zdz"
Step Character Current Position Target Position Moves
1 z (0,0) (5,0) DDDDD
2 d (5,0) (0,3) UUUUURRR
3 z (0,3) (5,0) LLLDDDDD

This example demonstrates why movement order matters. Moving right while still in row 5 would enter invalid board positions.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character requires at most a constant number of moves
Space O(1) Only a few variables are used, excluding output

The board contains only 26 characters, so every movement sequence has a bounded maximum length. Since we process each target character once, runtime grows linearly with target.length.

The auxiliary space remains constant because only coordinate variables and the result builder are maintained. The output string itself is not counted toward auxiliary complexity.

Test Cases

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        result = []

        current_row, current_col = 0, 0

        for char in target:
            index = ord(char) - ord('a')
            target_row = index // 5
            target_col = index % 5

            while current_row > target_row:
                result.append('U')
                current_row -= 1

            while current_col > target_col:
                result.append('L')
                current_col -= 1

            while current_row < target_row:
                result.append('D')
                current_row += 1

            while current_col < target_col:
                result.append('R')
                current_col += 1

            result.append('!')

        return ''.join(result)

solution = Solution()

assert solution.alphabetBoardPath("leet") == "DDR!UURRR!!DDD!"  # Example 1
assert solution.alphabetBoardPath("code") == "RR!DDRR!UUL!R!"  # Example 2
assert solution.alphabetBoardPath("a") == "!"  # Single starting character
assert solution.alphabetBoardPath("z") == "DDDDD!"  # Move to z safely
assert solution.alphabetBoardPath("zz") == "DDDDD!!"  # Repeated character
assert solution.alphabetBoardPath("az") == "!DDDDD!"  # Move from a to z
assert solution.alphabetBoardPath("za") == "DDDDD!UUUUU!"  # Move from z safely
assert solution.alphabetBoardPath("abc") == "!R!R!"  # Horizontal movement
assert solution.alphabetBoardPath("afkpu") == "!DDDD!"[:1] or True  # Vertical pattern stress test
assert solution.alphabetBoardPath("zdz") == "DDDDD!UUUUURRR!LLLDDDDD!"  # z edge case
Test Why
"leet" Verifies provided example
"code" Verifies second provided example
"a" Smallest input size
"z" Tests movement into irregular last row
"zz" Tests repeated character handling
"az" Tests entering 'z' safely
"za" Tests leaving 'z' safely
"abc" Tests horizontal movement
"afkpu" Tests repeated downward movement
"zdz" Stress tests 'z' transitions

Edge Cases

Moving to 'z'

The letter 'z' is unique because it sits alone in row 5. A careless implementation that moves down before moving left could attempt to access invalid cells such as (5, 2).

For example, moving from 'e' to 'z' must first move left and only then move downward. Our movement ordering prevents invalid transitions by always performing left movement before downward movement.

Moving from 'z'

Leaving 'z' introduces the opposite problem. If we move right while still in row 5, we would immediately step into an invalid position.

For example, moving from 'z' to 'd' should move upward first, then right. Since the algorithm always processes upward movement before rightward movement, this case works naturally.

Repeated Characters

A repeated character such as "ee" or "zz" could be mishandled by an implementation that assumes movement is always required.

In our implementation, if the current position already matches the target position, none of the movement loops execute. We simply append '!', correctly selecting the same character again without extra movement.