Word Ladder with One- or Two-Character Moves

Given a dictionary of words and a start and end word, decide whether a transformation path exists where each step changes one or two characters. Variant of classic word ladder with two-character moves added. Requirements Given a dictionary Set<String> words, a start word begin, and an end word end (all of equal length), determine whether there is a path begin → w_1 → w_2 → ... → end such that every intermediate word is in words and each step changes either exactly one character or exactly two characters. Return a boolean (path existence). The interviewer may follow up with reconstructing one valid path. The question typically ramps in three stages: (1) one-character reachability, (2) the one-or-two-character follow-up, (3) return an actual shortest path instead of a boolean. Watch these invariants, which are easy to miss: begin/start does not need to be in the dictionary. end/target is a valid final word even if it is not in the dictionary — add it to the candidate set explicitly. The dictionary may contain duplicates; treat it as a set. Filter to words of the same length as begin. Never revisit a word once explored. Notes The classic word ladder allows one-character changes and is solved by BFS over the implicit word graph. The two-character variant inflates the neighbor set per node from O(L · 25) to O(L · 25 + C(L,2) · 25²), where L is word length — still polynomial, but noticeably larger. BFS remains the canonical solution. The shortest-path property is not required (existence only), so a plain DFS with visited-set also works, but BFS is easier to reason about because the branching factor is bounded. Building the explicit neighbor list per word ahead of time is wasteful. Instead, generate neighbors lazily: for each position (or pair of positions), try every character substitution and check membership in words. For the two-character case, iterate over unordered position pairs and substitute both positions independently. Be careful to skip the no-op case (replacing each position with the same character — that is a zero-character change). Common interviewer follow-up: "what if we want the shortest path?" BFS gives this for free. "What if the dictionary has 1M words?" The bidirectional BFS (search from both ends, meet in the middle) is the standard answer and cuts the search space dramatically. Signatures and staged asks Typical OA-style signatures across the three stages (Python): def has_path_one_edit(start: str, target: str, words: list[str]) -> bool: ... def has_path_one_or_two_edits(start: str, target: str, words: list[str]) -> bool: ... def shortest_path_one_or_two_edits(start: str, target: str, words: list[str]) -> list[str]: ... The boolean variants return True/False for reachability. The path variant returns the shortest valid sequence inclusive of both start and target, or [] if no path exists. Neighbor-generation strategy: wildcard buckets vs. direct Hamming scan The classic one-character speedup precomputes wildcard buckets (h*t, *ot, …) so neighbors are found in O(L) hash lookups instead of scanning the dictionary. This is what makes Part 1 fast. The single-wildcard bucket trick does not extend cleanly to two-character moves. Once two-character jumps are allowed, the simplest interview-safe baseline is to keep the graph implicit and compare candidate words directly by Hamming distance (distance == 1 or distance == 2). Only the edge predicate changes between the one- and two-character parts; the BFS scaffold and complexity stay identical. The direct pairwise scan runs in O(n² · m) time, O(n) space (n = number of candidate words, m = word length) — the same asymptotic cost for the one- and two-character parts, since only the predicate differs. For short words and dense dictionaries this is the cleanest baseline; the lazy per-position generation above wins when the alphabet-substitution count is smaller than n. Reconstructing the path (Part 3) Once the ask becomes "return a shortest path," run BFS but keep a parent map (start → None); after target is dequeued (or matched), walk parents back from target and reverse. Return [] when target never enters the parent map. Because BFS explores in non-decreasing distance order, the reconstructed path is a shortest one. Preparation Drill classic Word Ladder (one-character variant) until it is muscle memory. The two-character extension layers on cleanly once the base is solid. Practice bidirectional BFS as the standard "large dictionary" follow-up answer. Be able to write it without a reference. Pre-decide the neighbor-enumeration strategy: lazy generation per position (cheap for short words, hot loop) vs precomputed neighbor sets (good for long words and dense dictionaries). For the interview length and typical word sizes, lazy generation is the right default. Be ready to swap the boolean BFS into a parent-map BFS on request, and to handle the start-not-in-dict / target-not-in-dict invariants without prompting.