1138. Alphabet Board Path

MediumHash TableString
Leetcode Link

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 or R) first to get to the correct column,
  • Then, move vertically (U or D) 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:

  1. Initialize your starting position as (0, 0), which corresponds to the top-left corner of the board, where 'a' is located.
  2. 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.
  3. 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'.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's consider a target word "dog". We will walk through the sequence of moves to spell "dog" on the alphabet board.

  1. The initial position is (0,0) for the character 'a'.
  2. 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 !.

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.


Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄