42. Shortest Query Reformulation

Problem

A customer's raw query token sometimes doesn't match any known query form exactly. Find the shortest sequence of single-character-edit reformulations from that raw token to a canonical known query token, where every intermediate reformulation along the way must also be a valid known query form.

This is the classic Word Ladder problem (LC127): BFS over single-character substitutions, stepping only through words in the known dictionary (all the same length as the begin/end words). The answer is the number of words in the shortest transformation sequence, including both the begin and end words, so a direct one-edit match returns 2. If the end word cannot be reached, return 0. Note that the end word must itself be in the dictionary to be reachable at all — the begin word need not be.

Source: src/42_shortest_query_reformulation.py

def shortest_reformulation(begin: str, end: str, word_dict: set[str]) -> int:
    ...

>>> shortest_reformulation("hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog"})
5

>>> shortest_reformulation("hit", "cog", {"hot", "dot", "dog", "lot", "log"})
0

>>> shortest_reformulation("hot", "dot", {"dot", "dog"})
2

Step-by-Step Approach

1. Short-circuit immediately: if end is not in word_dict, it can never be reached, so return 0 without doing any search.
2. Model the problem as a graph where each dictionary word (plus the begin word) is a node, and an edge connects two words that differ by exactly one character. The shortest transformation sequence is then a shortest path in this unweighted graph, which is exactly what BFS finds.
3. Initialize a queue with (begin, 1) — distance 1 because the count includes the begin word itself — and a visited set containing begin so it's never re-enqueued.
4. Pop from the front of the queue. If the current word equals end, return its distance immediately: BFS guarantees the first time you reach a node is via a shortest path.
5. Otherwise, generate every one-character variant of the current word (for each position, try all 25 other letters). For each variant that's in word_dict and not yet visited, mark it visited and enqueue it at dist + 1.
6. If the queue empties without ever reaching end, return 0 — unreachable.

The key insight is recognizing that "shortest sequence of valid single-step transformations" is a shortest-path problem in disguise; BFS explores the transformation graph level by level so the first arrival at the target is guaranteed to be via the fewest steps.

Reference solution

import string
from collections import deque


def shortest_reformulation(begin: str, end: str, word_dict: set[str]) -> int:
    # BFS over one-character substitutions, O(N * L * 26) time, N = len(word_dict), L = word length
    if end not in word_dict:
        return 0
    # set literal, O(1) membership tests
    visited = {begin}
    # deque: O(1) append/popleft, unlike list.pop(0)
    queue = deque([(begin, 1)])
    while queue:
        word, dist = queue.popleft()
        if word == end:
            return dist
        for i in range(len(word)):
            # built-in a-z constant, avoids hardcoding
            for c in string.ascii_lowercase:
                if c == word[i]:
                    continue
                # strings are immutable, rebuild via slicing
                candidate = word[:i] + c + word[i + 1 :]
                if candidate in word_dict and candidate not in visited:
                    visited.add(candidate)
                    queue.append((candidate, dist + 1))
    return 0

Key Functions & Tricks

• deque([(begin, 1)]) — O(1) append/popleft BFS queue, avoids O(n) list pop(0).
• queue.popleft() — O(1) FIFO dequeue from the front.
• string.ascii_lowercase — built-in "a"-"z" constant for iterating replacement letters.
• word[:i] + c + word[i + 1 :] — rebuilds a string with one char swapped (strings are immutable).
• {begin} — set literal for the visited set.
• candidate in word_dict / not in visited — O(1) average hash-based membership tests.

How to Recognize This Pattern