Skip to main content
Talentd

Alphabet Board Path - Solution & Explanation

MediumHash TableString11 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given an alphabet board where characters 'a' to 'y' form a 5x5 grid and 'z' sits alone on the next row. Starting at 'a', you must generate the sequence of moves (U, D, L, R) that navigates the board and presses ! for each character in a target string.

Approach 1: Direct Coordinate Mapping (Time: O(n), Space: O(1))

The board position of each letter is deterministic, so you can map every character to a coordinate (row, col). Iterate through the target string and compute the difference between the current position and the next character’s position. Move vertically and horizontally using repeated U/D/L/R operations, then append ! to select the character. The only tricky case is 'z', which sits at (5,0). When moving toward or away from 'z', prioritize up or left moves before down or right to avoid stepping into invalid cells of the board. The algorithm processes each character once, performing constant work per transition. Time complexity is O(n), where n is the target length, and space complexity is O(1) excluding the output string. This approach relies on simple coordinate math and works well with problems involving hash table lookups or direct character indexing.

Approach 2: Divide and Conquer Path Construction (Time: O(n), Space: O(log n) recursion)

This strategy treats the path generation problem as smaller independent segments. Split the target string into halves, recursively compute the path for each segment, then combine them while preserving the correct board position transitions. Each recursive step still uses coordinate differences to generate the path between characters, but the recursion structure allows modular path construction. While this does not improve asymptotic complexity, it can make implementations easier to reason about when composing path segments or integrating additional constraints. The algorithm still processes every character once, so the total time complexity remains O(n). Recursion introduces stack overhead, leading to O(log n) or O(n) auxiliary space depending on the split strategy. String manipulation is the main operation, making this approach closely tied to string processing patterns.

Recommended for interviews: Direct Coordinate Mapping is the expected solution. Interviewers want to see that you model the board with coordinates and carefully handle the 'z' edge case. A brute-force style navigation shows basic reasoning, but the coordinate-based approach demonstrates strong control over grid movement and constant-time character mapping.

Approach 1: Direct Coordinate Mapping

To solve this problem, we can map each character on the board to its respective coordinates. Then, for each character in the target, we calculate the necessary steps to move from the current position to the target character's position. A key consideration is to handle the movement to the character 'z' specifically, as it's only on the last row with a single column.

The provided Python solution creates a flat version of the board using a string, defines positions for each character, and iteratively navigates from the current position to the target character within a loop. Paths are appended in the form of a list that combines the necessary moves as well as an exclamation mark when the character is reached. The case of character 'z' is addressed separately.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the length of the target.
Space Complexity: O(1), except for the space needed for the output.

Try this approach in the editor →

Approach 2: Divide and Conquer

This approach leverages a divide and conquer strategy to optimize movement. By decomposing the problem into segments, starting each step towards the target character from the current board position provides clarity. Such decomposition aims to individually handle vertical and horizontal movements in separate phases.

This JavaScript solution first defines a function `charPos` to determine the board position of each character by referencing its ASCII value. For each character in the target string, a while loop strategically loads necessary movements (U, D, L, R), adjusting column and row indices (cx, cy) until arriving at the destination. The solution strives for clarity by separating tasks for different movement directions distinctly before appending '!' to complete each path section.

Code

JavaScriptC#

JavaScript

C#

Complexity

Time Complexity: O(n), where n is the length of the target.
Space Complexity: O(1), additional space use is minimal outside the result string itself.

Try this approach in the editor →

Approach 3: Simulation

Starting from the origin point (0, 0), simulate each step of the movement, appending the result of each step to the answer. Note that the direction of movement follows the order "left, up, right, down".

The time complexity is O(n), where n is the length of the string target, as each character in the string target needs to be traversed. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Coordinate Mapping

Time Complexity: O(n), where n is the length of the target.
Space Complexity: O(1), except for the space needed for the output.

Divide and Conquer

Time Complexity: O(n), where n is the length of the target.
Space Complexity: O(1), additional space use is minimal outside the result string itself.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Coordinate MappingO(n)O(1)Best general solution. Efficient when board coordinates can be computed directly.
Divide and Conquer Path ConstructionO(n)O(log n) recursionUseful when building paths in modular segments or experimenting with recursive string construction.

Video Solution

Alphabet board path problem (LeetCode #1138) - Inside code • Inside code • 6,846 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Alphabet Board Path easy or hard?
Alphabet Board Path is classified as a Medium problem. The core logic is straightforward, but handling the irregular board shape around 'z' introduces an edge case that often trips up first implementations. Careful ordering of moves ensures correctness.
Alphabet Board Path Python/Java solution
Both Python and Java implementations follow the same logic: compute coordinates for each character, move vertically and horizontally to reach the target letter, and append '!'. The implementation mainly consists of loops that append U, D, L, and R moves until the destination coordinate is reached.
How to solve Alphabet Board Path in O(n)?
Store or compute the (row, column) coordinates for each letter from 'a' to 'z'. Iterate through the target string and move from the current position to the next using U, D, L, and R operations based on coordinate differences. Handle the 'z' position carefully by moving up or left before moving down or right to avoid invalid cells.
What is the best approach for Alphabet Board Path?
Direct coordinate mapping is the best approach. Each character maps to a fixed row and column on the board, so you compute the vertical and horizontal differences between the current letter and the next one. This produces the move sequence in O(n) time with constant extra space. Special handling for the 'z' row avoids invalid board positions.
Is Alphabet Board Path asked at Google/Amazon/Meta?
Alphabet Board Path appears in interview preparation sets and online assessments at several large tech companies. It tests grid navigation, coordinate reasoning, and careful edge‑case handling. The problem difficulty aligns with medium-level string and simulation questions commonly asked in Amazon and Google-style interviews.
What data structure is used in Alphabet Board Path?
The solution typically uses simple coordinate mapping, which can be implemented with a hash table or direct arithmetic from the character index. Strings are used to build the final path sequence. No complex data structures are required beyond basic lookups and iteration.
What is the time complexity of Alphabet Board Path?
The optimal solution runs in O(n) time where n is the length of the target string. Each character requires calculating coordinate differences and appending a few directional moves. Space complexity is O(1) excluding the output path string.

Ready to solve this problem?

Practice Alphabet Board Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters