Alphabet Board Path

medium string simulation grid

Problem

On an alphabet board, letters a–z are laid out in a 5-row grid: row r, column c holds letter index r*5 + c (so 'a' is at (0,0) and 'z' is at (5,0)). You start at 'a'. To spell a word you may move U (up), D (down), L (left), R (right), and press ! to select the current letter. Return any sequence of moves that spells the word. The catch: 'z' sits alone on its own row, so you must never step off the board while passing over the gap.

Inputtarget = "leet"

Output"DDR!UURRR!!DDD!"

From 'a'(0,0): DDR to 'l'(2,1) then !; UURRR to 'e'(0,4) then !; ! again for the second 'e'; DDD to 't'(3,4) then !. Any valid sequence is accepted.

target (lowercase letters)

def alphabet_board_path(target):
    res = []
    r, c = 0, 0
    for ch in target:
        nr, nc = divmod(ord(ch) - ord('a'), 5)
        if nc < c: res.append('L' * (c - nc))
        if nr < r: res.append('U' * (r - nr))
        if nr > r: res.append('D' * (nr - r))
        if nc > c: res.append('R' * (nc - c))
        res.append('!')
        r, c = nr, nc
    return ''.join(res)

function alphabetBoardPath(target) {
  const res = [];
  let r = 0, c = 0;
  for (const ch of target) {
    const idx = ch.charCodeAt(0) - 97;
    const nr = Math.floor(idx / 5), nc = idx % 5;
    if (nc < c) res.push('L'.repeat(c - nc));
    if (nr < r) res.push('U'.repeat(r - nr));
    if (nr > r) res.push('D'.repeat(nr - r));
    if (nc > c) res.push('R'.repeat(nc - c));
    res.push('!');
    r = nr; c = nc;
  }
  return res.join('');
}

class Solution {
    public String alphabetBoardPath(String target) {
        StringBuilder sb = new StringBuilder();
        int r = 0, c = 0;
        for (char ch : target.toCharArray()) {
            int idx = ch - 'a';
            int nr = idx / 5, nc = idx % 5;
            while (c > nc) { sb.append('L'); c--; }
            while (r > nr) { sb.append('U'); r--; }
            while (r < nr) { sb.append('D'); r++; }
            while (c < nc) { sb.append('R'); c++; }
            sb.append('!');
        }
        return sb.toString();
    }
}

string alphabetBoardPath(string target) {
    string res;
    int r = 0, c = 0;
    for (char ch : target) {
        int idx = ch - 'a';
        int nr = idx / 5, nc = idx % 5;
        while (c > nc) { res += 'L'; c--; }
        while (r > nr) { res += 'U'; r--; }
        while (r < nr) { res += 'D'; r++; }
        while (c < nc) { res += 'R'; c++; }
        res += '!';
    }
    return res;
}

Explanation

This is a simulation: we keep our current position (r, c) on the board and, for each target letter, emit the moves to get there, then press !. The only real subtlety is the lonely z, which sits by itself on the bottom row.

Each letter's spot is found from its alphabet index: row is index / 5 and column is index % 5. To travel from the current cell to the target we add the right number of L, U, D, or R moves to cover the row and column difference.

The order of the moves is the trick. We do L (left) and U (up) before D (down) and R (right). Moving up and left first guarantees we step off z's isolated cell before ever trying to move right (which has no neighbour there), so we never leave the board.

Example: target = "leet". From a(0,0) to l(2,1): go DDR then !. To e(0,4): UURRR!. The second e is already there, so just !. To t(3,4): DDD!.

Concatenating each step's moves and presses yields a full valid path; any correct sequence is accepted.

Time: O(n) Space: O(n)