Skip to main content

Hashing

Alphabet Board Path Solution In C++/Java/Python/JS

Problem Description

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].
Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].
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.

Examples:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

  • 1 <= target.length <= 100
  • target consists only of English lowercase letters.
💡
Try it Yourself First!
The Alphabet Board Path problem requires navigating a 5x5 grid of letters ('a' to 'z') to spell a given string using the shortest path. The challenge lies in handling movement constraints, especially for 'z,' which is isolated in the last row. The key approach is to compute row and column differences, move vertically before horizontally to avoid invalid moves, and append necessary steps efficiently. This problem strengthens understanding of grid traversal and coordinate-based movement logic.

Optimal Approach

To understand the Alphabet Board Path problem, let's break it down step by step. Imagine you have a 5x5 board with letters from 'a' to 'z' arranged row-wise, except for 'z', which is isolated at the bottom. You start at 'a' (top-left) and need to generate the shortest sequence of moves (up, down, left, right) to reach each letter in the target string, pressing '!' when reaching the correct letter.

The first step is determining the (row, column) position of each character. The formula (ch - 'a') / 5 gives the row, and (ch - 'a') % 5 gives the column. Once we find the target letter's position, we need to navigate the board efficiently. A key observation is that moving up ('U') and left ('L') should always be done first before moving down or right. This prevents invalid moves when dealing with 'z', which is isolated in the last row with no right neighbor.

The movement logic follows a structured approach:

  • Move up ('U') first if needed.
  • Move left ('L') if the target column is smaller.
  • Move down ('D') next if required.
  • Move right ('R') last.
    Once the correct position is reached, we append '!' to mark character selection. The loop repeats for all characters in target, ensuring an optimal path.

This approach is efficient with an O(n) time complexity, as we traverse the string once and take constant moves per character. The space complexity is O(n), storing the output path. By following this structured movement, we avoid unnecessary steps and ensure the shortest possible path to each letter.

Approach

Step 1: Initialize Variables

  • Create an empty string result to store the path.
  • Start at position (0,0), which corresponds to the letter 'a'.
  • currX = 0, currY = 0 represents our current position on the board.

Step 2: Iterate Over Each Character in target

  • Loop through each letter in the input string target.
  • Find the position of the letter in the 5x5 grid using:
    • Row (targetX) = (ch - 'a') / 5
    • Column (targetY) = (ch - 'a') % 5

Step 3: Move to the Target Position

Since movement is restricted and 'z' is isolated, we move in a structured order:

1. Move Up (U) First

  • If currX > targetX, move up (U) step-by-step.
  • This is necessary to prevent moving right/down into an invalid position (like around 'z').

2. Move Left (L) Second

  • If currY > targetY, move left (L) to reach the correct column.

3. Move Down (D) Third

  • If currX < targetX, move down (D) to reach the correct row.

4. Move Right (R) Last

  • If currY < targetY, move right (R) step-by-step.

Step 4: Mark the Letter as Reached

  • Once we arrive at the target letter's position, append '!' to indicate selection.
  • Update currX and currY to the new position.

Step 5: Repeat Until All Letters Are Processed

  • The loop continues until all letters in target are processed.
  • The final result string contains the path.

Alphabet Board Path Dry run - Optimised

Input: target = "leet"
Step 1: Initialize

  • Start at 'a' at (0,0)
  • Initialize currX = 0, currY = 0
  • Initialize result = ""

Step 2: Process Each Character in "leet"
Move to 'l' (2,1)

    • 'l' is at (2,1)
    • Move down (D) to (1,0), result = "D"
    • Move down (D) to (2,0), result = "DD"
    • Move right (R) to (2,1), result = "DDR"
    • Append !, result = "DDR!"
    • Update currX = 2, currY = 1

Move to 'e' (0,4)

    • 'e' is at (0,4)
    • Move up (U) to (1,1), result = "DDR!U"
    • Move up (U) to (0,1), result = "DDR!UU"
    • Move right (R) to (0,2), result = "DDR!UUR"
    • Move right (R) to (0,3), result = "DDR!UURR"
    • Move right (R) to (0,4), result = "DDR!UURRR"
    • Append !, result = "DDR!UURRR!"
    • Update currX = 0, currY = 4

Move to 'e' Again (0,4)

    • Already at (0,4)
    • Append !, result = "DDR!UURRR!!"

Move to 't' (3,4)

    • 't' is at (3,4)
    • Move down (D) to (1,4), result = "DDR!UURRR!!D"
    • Move down (D) to (2,4), result = "DDR!UURRR!!DD"
    • Move down (D) to (3,4), result = "DDR!UURRR!!DDD"
    • Append !, result = "DDR!UURRR!!DDD!"
    • Update currX = 3, currY = 4

Final Output: "DDR!UURRR!!DDD!"

Alphabet Board Path Code for All Languages - Optimised
C++ 
class Solution {
public:
    string alphabetBoardPath(string target) {
        string result = "";
        
        // Starting position at 'a' (0,0)
        int currX = 0, currY = 0;
        
        // Process each letter in target string
        for (char ch : target) {
            
            // Find the target character's position on the board
            int targetX = (ch - 'a') / 5;
            int targetY = (ch - 'a') % 5;
            
            // Move step by step to the target position
            
            // Move up first (avoid invalid 'z' cases)
            while (currX > targetX) {
                result += 'U';
                currX--;
            }
            
            // Move left
            while (currY > targetY) {
                result += 'L';
                currY--;
            }
            
            // Move down
            while (currX < targetX) {
                result += 'D';
                currX++;
            }
            
            // Move right
            while (currY < targetY) {
                result += 'R';
                currY++;
            }
            
            // Append '!' after reaching the character
            result += '!';
        }
        
        return result;
    }
};

Alphabet Board Path Code in Java - Optimised 
class Solution {
    public String alphabetBoardPath(String target) {
        StringBuilder result = new StringBuilder();
        int prevX = 0, prevY = 0;

        for (char c : target.toCharArray()) {
            int currX = (c - 'a') % 5;
            int currY = (c - 'a') / 5;

            // Move up first before moving left to avoid "z" corner case
            while (prevY > currY) {
                result.append("U");
                prevY--;
            }
            while (prevX > currX) {
                result.append("L");
                prevX--;
            }
            while (prevY < currY) {
                result.append("D");
                prevY++;
            }
            while (prevX < currX) {
                result.append("R");
                prevX++;
            }

            // Select the letter
            result.append("!");
        }
        return result.toString();
    }
}

Alphabet Board Path Code in Python - Optimised 
class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        result = []
        prev_x, prev_y = 0, 0
        
        for c in target:
            curr_x, curr_y = (ord(c) - ord('a')) % 5, (ord(c) - ord('a')) // 5

            # Move up first before moving left to avoid "z" corner case
            while prev_y > curr_y:
                result.append("U")
                prev_y -= 1
            while prev_x > curr_x:
                result.append("L")
                prev_x -= 1
            while prev_y < curr_y:
                result.append("D")
                prev_y += 1
            while prev_x < curr_x:
                result.append("R")
                prev_x += 1

            # Select the letter
            result.append("!")

        return "".join(result)

Alphabet Board Path Code in Javascript - Optimised 
class Solution {
    alphabetBoardPath(target) {
        let result = [];
        let prevX = 0, prevY = 0;

        for (let c of target) {
            let currX = (c.charCodeAt(0) - 'a'.charCodeAt(0)) % 5;
            let currY = Math.floor((c.charCodeAt(0) - 'a'.charCodeAt(0)) / 5);

            // Move up first before moving left to avoid "z" corner case
            while (prevY > currY) {
                result.push("U");
                prevY--;
            }
            while (prevX > currX) {
                result.push("L");
                prevX--;
            }
            while (prevY < currY) {
                result.push("D");
                prevY++;
            }
            while (prevX < currX) {
                result.push("R");
                prevX++;
            }

            // Select the letter
            result.push("!");
        }
        return result.join("");
    }
}

Time Complexity: O(n)

We iterate through the target string once, and for each character, we make a constant number of movements, so the overall time complexity remains O(n).

Space Complexity: O(n)

  • Auxiliary Space: O(n) → The result string stores the movement sequence.
  • Total Space Complexity: O(n) → Since we store only the output string, the space usage is proportional to n.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Snapshot Array

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
  • void set(index, val) sets the element at the given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id