0

Spell a word on a 5-column letter board

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Spell a word on a 5-column letter board

Companies: Microsoft

Difficulty: Medium

Problem statement

A text-entry device shows the 26 lowercase letters on a board 5 columns wide, filled row by row. Letter c sits at row (ord(c) - ord('a')) // 5 and column (ord(c) - ord('a')) % 5:

    0 1 2 3 4
0   a b c d e
1   f g h i j
2   k l m n o
3   p q r s t
4   u v w x y
5   z

The last row holds only z. The cells to its right do not exist, and the cursor may never move onto them or off the board.

The cursor starts on a at (0, 0). It accepts five commands:

  • U, D, L, R: move one cell up, down, left or right.
  • !: select the letter under the cursor.

Implement word_path(word: str) -> str. It returns a command string that types word using the fewest possible moves. Any shortest answer is accepted.

Constraints

  • 0 <= len(word) <= 100
  • word contains only lowercase English letters.

Example 1

word_path("bad")  ->  "R!L!RRR!"

Move right to b and select it, move left to a and select it, then move right three cells to d.

Example 2

word_path("oz")  ->  "DDRRRR!LLLLDDD!"

o is at (2, 4). To reach z the cursor must move left to column 0 before it moves down. Moving down first would step onto a missing cell in row 5.

Approach

Every letter has a fixed cell: letter c with index i = ord(c) - ord('a') sits at
row i // 5, column i % 5. So the problem is: walk from (0, 0) through the
cells of the target word in order, emit a move string for each hop, and emit !
each time you land on the letter you need.

Brute force. Treat the board as a graph and run a BFS from the current cell
to the next letter's cell, then rebuild the path from parent pointers. That is
always correct, including around the ragged last row, but it does O(26) work
per letter for something that has a closed form. It is still worth naming,
because it is the version that survives if the board stops being a clean grid
(see Follow-ups).

Optimal: Manhattan moves in a safe order. On a full rectangle any
interleaving of |dr| vertical and |dc| horizontal moves is a shortest path.
The only trap is row 5, which holds just z at column 0. Cells (5, 1..4) do
not exist, so a path may never pass through them:

  • Going to z from column > 0: move left first, then down. Moving down
    first would step from (4, c) into the missing cell (5, c).
  • Going from z to column > 0: move up first, then right. Moving right
    first would step from (5, 0) into (5, 1).

Emitting moves in the order U, L, D, R satisfies both rules at once:
up and left only ever take you toward the full part of the board, and by the
time you go down you are already in the column you need. Every valid cell in
column 0 exists down to row 5, so the down moves are safe; every row from 0 to 4
is full, so the right moves are safe.

Invariants.

  • The cursor is always on an existing cell.
  • After processing the k-th letter, the cursor is on that letter's cell and the
    output has exactly k ! characters.
  • Each hop uses exactly |dr| + |dc| moves, so the total path is shortest.

Code

from typing import Tuple

WIDTH = 5


def position(ch: str) -> Tuple[int, int]:
    if len(ch) != 1 or not ("a" <= ch <= "z"):
        raise ValueError(f"not a lowercase letter: {ch!r}")
    idx = ord(ch) - ord("a")
    return divmod(idx, WIDTH)


def word_path(word: str) -> str:
    """Return a shortest move string (U/D/L/R, '!' to select) spelling word."""
    row, col = 0, 0
    out: list[str] = []
    for ch in word:
        tr, tc = position(ch)
        # Order U, L, D, R keeps us off the missing cells (5, 1..4).
        if tr < row:
            out.append("U" * (row - tr))
        if tc < col:
            out.append("L" * (col - tc))
        if tr > row:
            out.append("D" * (tr - row))
        if tc > col:
            out.append("R" * (tc - col))
        out.append("!")
        row, col = tr, tc
    return "".join(out)


def replay(path: str) -> str:
    """Simulate a move string; raise if it ever leaves the board."""
    row, col = 0, 0
    deltas = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
    spelled: list[str] = []
    for move in path:
        if move == "!":
            spelled.append(chr(ord("a") + row * WIDTH + col))
            continue
        dr, dc = deltas[move]
        row, col = row + dr, col + dc
        if not (0 <= col < WIDTH and 0 <= row and row * WIDTH + col < 26):
            raise ValueError(f"stepped off the board at ({row}, {col})")
    return "".join(spelled)


if __name__ == "__main__":
    assert word_path("") == ""
    assert word_path("a") == "!"
    assert word_path("aa") == "!!"
    assert word_path("bad") == "R!L!RRR!"
    assert word_path("z") == "DDDDD!"
    assert word_path("oz") == "DDRRRR!LLLLDDD!"
    assert word_path("zy") == "DDDDD!URRRR!"
    assert word_path("yz") == "DDDDRRRR!LLLLD!"
    for w in ["zdz", "leetcode", "code", "zzzyxz", "abcdefghijklmnopqrstuvwxyz"]:
        p = word_path(w)
        assert replay(p) == w
        # Shortest: moves equal the sum of Manhattan distances.
        cells = [(0, 0)] + [position(c) for c in w]
        dist = sum(abs(a[0] - b[0]) + abs(a[1] - b[1]) for a, b in zip(cells, cells[1:]))
        assert len(p) - len(w) == dist
    print("ok")

Complexity

  • position: O(1) time and space.
  • word_path: O(n + M) time, where n is the word length and M the total
    number of moves. Each hop is at most 5 + 4 = 9 moves, so M <= 9n and the
    whole thing is O(n). Output space O(n); no other state beyond the cursor.
  • BFS alternative: O(n * V) time with V = 26 cells, O(V) extra space per hop.

Test cases

  • "" returns "" (nothing to spell).
  • "a" returns "!" (already standing on it).
  • "aa" returns "!!" (repeated letter, no moves between).
  • "bad" returns "R!L!RRR!".
  • "z" returns "DDDDD!" (straight down column 0).
  • "oz": o is (2, 4). Returns "DDRRRR!LLLLDDD!"; left before down when entering z.
  • "zy" returns "DDDDD!URRRR!"; up before right when leaving z.
  • "yz" returns "DDDDRRRR!LLLLD!".
  • "zdz": replaying the output never touches (5, 1..4) and spells "zdz".
  • "A" or "1" raises ValueError (input outside the alphabet).
  • Full alphabet: the move count equals the sum of Manhattan distances between
    consecutive letters, so the path is shortest.

Follow-ups

  1. Configurable width (k columns). Replace WIDTH = 5 with a parameter.
    The U, L, D, R order still works for any width, because only the last row is
    partial and it is always filled from the left.
  2. Blocked or arbitrary layout (keys missing in the middle, a phone keypad,
    QWERTY rows of different lengths). The closed form breaks; switch to BFS per
    hop on a char -> (row, col) map plus a set of valid cells. Cache the
    shortest path between every pair of letters (26 x 26) if many words are
    spelled.
  3. Minimize something else, e.g. direction changes or a cost per move type.
    Use Dijkstra over states (cell, last_direction); the U, L, D, R grouping
    already gives at most two direction changes per hop on the clean board.
  4. Return all shortest paths or count them. For each hop the count is
    C(|dr| + |dc|, |dr|) on a full rectangle, minus the paths through missing
    cells; generate them with DFS over the Manhattan moves, pruning invalid cells.
    Multiply the per-hop counts for the word.
  5. Wraparound or diagonal moves. With wraparound, horizontal distance becomes
    min(d, width - d); with diagonals, it becomes Chebyshev distance and the
    missing-cell checks need to cover diagonal steps too.

Interviewer expectations

Mid-level (L4)

  • Maps letters to coordinates with divmod instead of hardcoding a grid.
  • Produces correct moves for ordinary letters and handles '!' and repeats.
  • Finds the z corner case, at least after a hint, and fixes the move order.

Senior (L5)

  • Spots the missing cells before coding and explains why U, L, D, R is safe in
    both directions.
  • Argues the path is shortest (Manhattan distance is a lower bound and is met).
  • Writes a replay or validator to test the output, and covers empty input and
    invalid characters.

Staff (L6+)

  • Separates the layout from the routing so a new keyboard is a data change.
  • Knows when the closed form stops working and moves to BFS, with precomputed
    all-pairs paths for throughput.
  • Discusses alternative cost models (direction changes, wraparound) and how the
    state space grows for each.

Sign in to comment, vote or remix.