1138. Alphabet Board Path
Problem Description
In this problem, we are given a representation of an alphabet board as a list of strings, where each string corresponds to a row on the board. The board is laid out such that the top left corner corresponds to "a"
and letters continue in alphabetical order from left to right and then top to bottom, ending with "z"
on its own row.
The task is to navigate this board starting from the top left corner (0, 0)
to spell out a given target word. We can move one step in the four cardinal directions: up (U
), down (D
), left (L
), right (R
), but only within the limits of the board. We append a letter to our output by reaching its position on the board and issuing an exclamation mark (!
).
We are required to find and return a sequence of moves that will result in the target word in the minimum number of moves possible. Note that there may be multiple valid sequences that will result in the target word, and any such valid sequence is acceptable.
Intuition
To approach this problem, we should think about it as navigating a 2D grid, translating our desired string into a series of coordinates. The key insight is to map each character of the target to its coordinate on the board and then determine the series of moves to reach from one character to the next.
The intuition behind the given solution is that for each character in the target string, we calculate its position (x, y)
on the board. Since x
is the row and y
is the column, we get:
x
as the quotient of the division of the character’s index in the alphabet by the number of columns,y
as the remainder of the same division.
Once we have the target position for the current character, we execute a specific order of moves:
- Move horizontally (
L
orR
) first to get to the correct column, - Then, move vertically (
U
orD
) to get to the correct row.
This order of moves is important, especially when dealing with the character "z"
. Since "z"
is located at the bottom of the board and has no right neighbor, if we needed to go right after moving down to "z"
, it would be impossible. Moving horizontally first at other locations ensures that we never encounter a scenario where we cannot make the next move.
After moving to the correct position, we append an exclamation mark (!
) to signify that we have 'typed' the character. We repeat this process for each character in the target string. The concatenation of all the instructions yields our result.
The overall strategy is straightforward and intuitive when we recognize that each letter corresponds to a grid location, and we need to navigate this grid in an efficient manner.
Solution Approach
The solution uses a simple simulation approach with no fancy data structures or algorithms required. The key is to understand the direct correspondence between characters and their positions on the board and how to translate between characters and positions.
The algorithm goes as follows:
- Initialize your starting position as
(0, 0)
, which corresponds to the top-left corner of the board, where'a'
is located. - For each character in the
target
string:- Compute the character's row (
x
) and column (y
) based on its ASCII value subtracted by the ASCII value of'a'
. - Horizontal move: If the current position's column (
j
) is greater than the target character's column (y
), add'L'
(left) moves until both columns match; else if it's less, add'R'
(right) moves. This is done to ensure we are at the correct column before adjusting the row, which is important due to the last row having only'z'
. - Vertical move: Similarly, if the current position's row (
i
) is greater than the target character's row (x
), add'U'
(up) moves until both rows match; else if it's less, add'D'
(down) moves. This brings us to the correct row. - Once at the correct position, append
'!'
to "type" the character.
- Compute the character's row (
- Repeat this procedure for all characters in the
target
.
The pseudocode for the part of the code that determines the movements is:
1for c in target:
2 v = ord(c) - ord('a') # The ASCII difference gives us the linear index
3 x, y = v // 5, v % 5 # Translate linear index to 2D board coords (5 columns)
4
5 # Ensure to move horizontally first to handle 'z' special case
6 while (current col) > (target col):
7 move left
8 append "L" to path
9
10 while (current row) > (target row):
11 move up
12 append "U" to path
13
14 while (current col) < (target col):
15 move right
16 append "R" to path
17
18 while (current row) < (target row):
19 move down
20 append "D" to path
21
22 # At target position, 'type' the character
23 append "!" to path
The function uses a list ans
to keep track of the path, appending directions as it figures out the moves required. At the end of the loop for each character, the answer list is joined into a string to provide the final sequence of moves.
The key takeaway is that the algorithm effectively decouples the horizontal and vertical movements. It treats the problem as instructions to navigate to a 2D point from another 2D point within given constraints, ensuring that we do not get stuck in any edge cases, particularly with the isolated 'z'
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a target word "dog". We will walk through the sequence of moves to spell "dog" on the alphabet board.
- The initial position is
(0,0)
for the character'a'
. - The target string is "dog":
- The first character is
d
, and its 2D board coordinates are (3 // 5, 3 % 5) = (0, 3) since 'd' is the 3rd letter ('a' being indexed at 0). - From
(0,0)
we need to move right ('R') 3 times to get to(0,3)
. - We "type"
d
by appending!
. - The second character is
o
, with coordinates (14 // 5, 14 % 5) = (2, 4). - We need to move down ('D') 2 times to get to row 2, and then move right ('R') 1 time to get to column 4.
- We "type"
o
by appending!
. - The third character is
g
, with coordinates (6 // 5, 6 % 5) = (1, 1). - Since we cannot move directly left from
z
if we were there, and we're dealing with the general algorithm now, we should move up ('U') 1 time first, then move left ('L') 3 times to get to column 1 and down ('D') 1 time to get to row 1. - We "type"
g
by appending!
.
- The first character is
Putting it all together, the path to spell "dog" would be "RRR!DDDR!UULLD!". This is the series of moves following the described solution approach:
- Start at
a
(initial position). - For
d
: move right 3 times (RRR
), "type" (!
). - For
o
: move down 2 times (DD
), move right 1 time (R
), "type" (!
). - For
g
: move up 1 time (U
), move left 3 times (LLL
), move down 1 time (D
), "type" (!
).
This example illustrates how the algorithm navigates through each character in the target word, considering the special layout of the alphabet board and the isolated position of 'z'
.
Solution Implementation
1class Solution:
2 def alphabetBoardPath(self, target: str) -> str:
3 # initial position on the alphabet board
4 row, col = 0, 0
5 answer = []
6 for char in target:
7 # calculate the target's position on the 5x5 board
8 target_value = ord(char) - ord('a')
9 target_row, target_col = divmod(target_value, 5)
10
11 # Since for 'z', the board needs to go all the way down before going right,
12 # make sure to move left before moving down.
13 while col > target_col:
14 col -= 1
15 answer.append("L")
16
17 while row > target_row:
18 row -= 1
19 answer.append("U")
20
21 while col < target_col:
22 col += 1
23 answer.append("R")
24
25 # This part is for moving down to reach the target row,
26 # which is placed after left and right moves to handle 'z' correctly.
27 while row < target_row:
28 row += 1
29 answer.append("D")
30
31 # append '!' after reaching the correct alphabet position
32 answer.append("!")
33
34 # join the list into a string to provide the path sequence
35 return "".join(answer)
36
1class Solution {
2 public String alphabetBoardPath(String target) {
3 // StringBuilder to keep track of the path
4 StringBuilder path = new StringBuilder();
5
6 // Starting position on the board (top-left corner: 'a')
7 int currentRow = 0, currentCol = 0;
8
9 // Iterate through each character in the target string
10 for (int k = 0; k < target.length(); ++k) {
11 // Get the board position for the target character
12 int targetPos = target.charAt(k) - 'a';
13 // Calculate the row and column on the board
14 int targetRow = targetPos / 5, targetCol = targetPos % 5;
15
16 // Move left while the current column is to the right of the target column
17 while (currentCol > targetCol) {
18 --currentCol;
19 path.append('L');
20 }
21 // Move up while the current row is below the target row
22 while (currentRow > targetRow) {
23 --currentRow;
24 path.append('U');
25 }
26 // Move right while the current column is to the left of the target column
27 while (currentCol < targetCol) {
28 ++currentCol;
29 path.append('R');
30 }
31 // Move down while the current row is above the target row
32 while (currentRow < targetRow) {
33 ++currentRow;
34 path.append('D');
35 }
36
37 // Add an exclamation point to indicate that the target letter is selected
38 path.append("!");
39 }
40
41 // Return the full path as a string
42 return path.toString();
43 }
44}
45
1class Solution {
2public:
3 string alphabetBoardPath(string target) {
4 string path; // This will hold the final path sequence.
5 int currentRow = 0, currentCol = 0; // Starting position at the top-left corner of the board ('a').
6
7 for (const char &character : target) {
8 int targetPosition = character - 'a'; // Calculate the numeric position in the alphabet.
9 int targetRow = targetPosition / 5; // Calculate the target row.
10 int targetCol = targetPosition % 5; // Calculate the target column.
11
12 // Move left if necessary.
13 while (currentCol > targetCol) {
14 --currentCol;
15 path += 'L';
16 }
17 // Move up if necessary.
18 while (currentRow > targetRow) {
19 --currentRow;
20 path += 'U';
21 }
22 // Move right if necessary.
23 while (currentCol < targetCol) {
24 ++currentCol;
25 path += 'R';
26 }
27 // Move down if necessary.
28 while (currentRow < targetRow) {
29 ++currentRow;
30 path += 'D';
31 }
32 // Add an exclamation point to mark the arrival at the target character.
33 path += '!';
34 }
35 // Return the completed path sequence.
36 return path;
37 }
38};
39
1function alphabetBoardPath(target: string): string {
2 let path: string = ""; // This will hold the final path sequence.
3 let currentRow: number = 0; // Start position's row at the top-left corner of the board ('a').
4 let currentCol: number = 0; // Start position's column at the top-left corner of the board ('a').
5
6 for (const character of target) {
7 const targetPosition: number = character.charCodeAt(0) - 'a'.charCodeAt(0); // Calculate the numeric position in the alphabet.
8 const targetRow: number = Math.floor(targetPosition / 5); // Calculate the target row.
9 const targetCol: number = targetPosition % 5; // Calculate the target column.
10
11 // Due to how 'z' is positioned, the 'L' and 'U' moves must be prioritized over 'R' and 'D' to avoid invalid moves
12
13 // Move left if necessary
14 while (currentCol > targetCol) {
15 currentCol--;
16 path += 'L';
17 }
18
19 // Move up if necessary
20 while (currentRow > targetRow) {
21 currentRow--;
22 path += 'U';
23 }
24
25 // Move right if necessary
26 while (currentCol < targetCol) {
27 currentCol++;
28 path += 'R';
29 }
30
31 // Move down if necessary
32 while (currentRow < targetRow) {
33 currentRow++;
34 path += 'D';
35 }
36
37 // Add an exclamation point to mark the arrival at the target character
38 path += '!';
39 }
40
41 // Return the completed path sequence
42 return path;
43}
44
Time and Space Complexity
The Solution provided above has a time complexity of O(n)
, where n
is the length of the input string target
. This is because the algorithm must iterate over each character in the target
string once, and for each character, it performs a constant amount of work: calculating x
and y
coordinates, then moving horizontally and vertically on the board.
The space complexity of the code is O(n)
as well, primarily due to the ans
list that collects the sequence of moves. The length of ans
directly corresponds to the number of moves, which is proportional to the number of characters in the target
string because for each character, the code appends several movements (up to 4 direction changes plus one "!" per character) to the ans
list.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.