Alphabet Board Path - Practice Coding Problems

Alphabet Board Path - Problem

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

Note: 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.

Input & Output

Example 1 — Basic Navigation

$ Input: target = "leet"

› Output: "DDR!UURRR!DDRR!UUL!"

💡 Note: Start at 'a'(0,0). Go to 'l'(2,1): DD(down 2)R(right 1)!. Go to 'e'(0,4): UU(up 2)RRR(right 3)!. Go to 'e'(0,4): already there!. Go to 't'(3,4): DD(down 2)R(right 1)R(right 1)!. Go to 't'(3,4): already there but need UUL to simulate path calculation: UUL!

Example 2 — Edge Case with 'z'

$ Input: target = "zdz"

› Output: "DDDDD!UUUUURRRR!DDDD!"

💡 Note: Start at 'a'(0,0). Go to 'z'(5,0): DDDDD(down 5)!. Go to 'd'(0,3): UUUUU(up 5)RRR(right 3)!. Go to 'z'(5,0): DDDD(down 4, special handling)!

Example 3 — Single Character

$ Input: target = "a"

› Output: "!"

💡 Note: Already at 'a'(0,0), just add '!' to collect the character

Constraints

1 ≤ target.length ≤ 100
target consists only of English lowercase letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Target string 'leet' to spell on alphabet board

Process

Calculate Manhattan distance paths between characters

Output

Movement sequence: DDR!UURRR!DDRR!UUL!

Key Takeaway

🎯 Key Insight: Use coordinate mapping and Manhattan distance for direct path calculation between any two characters

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is to use coordinate mapping with Manhattan distance calculation. Pre-compute each character's (row, col) position, then for each target character, calculate the direct path using row and column differences. Handle the 'z' edge case by moving up before left. Best approach uses Hash Map with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with BFS	O(n × 26²)	O(26)	Use BFS to find shortest path between each pair of characters
Hash Map with Coordinate Mapping	O(n)	O(1)	Pre-compute character coordinates, then calculate Manhattan distances

Brute Force with BFS — Algorithm Steps

For each character in target, use BFS from current position
Explore all valid moves (U,D,L,R) level by level
Stop when target character is reached
Record the path and add '!' to collect character

Visualization

Tap to expand

Step-by-Step Walkthrough

Start BFS

Begin search from current position

Explore Moves

Try all valid directions (U,D,L,R) level by level

Find Target

Return path when target character is reached

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* target) {
    char board[6][6] = {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
    int boardRows = 6;
    int boardCols[6] = {5, 5, 5, 5, 5, 1};
    
    char* result = (char*)malloc(10000 * sizeof(char));
    result[0] = '\0';
    int currR = 0, currC = 0;
    
    for (int i = 0; i < strlen(target); i++) {
        char targetChar = target[i];
        
        // Find target character position
        int targetR = -1, targetCol = -1;
        for (int r = 0; r < boardRows; r++) {
            for (int c = 0; c < boardCols[r]; c++) {
                if (board[r][c] == targetChar) {
                    targetR = r; targetCol = c;
                    break;
                }
            }
            if (targetR != -1) break;
        }
        
        // Simple Manhattan distance path
        while (currR != targetR) {
            if (currR < targetR) {
                strcat(result, "D");
                currR++;
            } else {
                strcat(result, "U");
                currR--;
            }
        }
        while (currC != targetCol) {
            if (currC < targetCol) {
                strcat(result, "R");
                currC++;
            } else {
                strcat(result, "L");
                currC--;
            }
        }
        
        strcat(result, "!");
    }
    
    return result;
}

int main() {
    char target[1000];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    char* result = solution(target);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 26²)

For n characters in target, each BFS explores up to 26 positions in worst case

✓ Linear Growth

Space Complexity

O(26)

BFS queue stores at most 26 board positions

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler