381. Word Ladder - Shortest Transformation Length

Given a start word, an end word, and a dictionary of k words (all words, including start and end, are the same length and made only of lowercase letters), find the length (number of words, including both start and end) of the shortest sequence of dictionary words that transforms start into end, changing exactly one letter at a time, where every intermediate word must be in the dictionary. Print 0 if no such transformation exists (this includes when end itself isn't in the dictionary).

Input: The first line contains the start word. The second line contains the end word. The third line contains an integer k, the dictionary size. Each of the next k lines contains one dictionary word. Output: Print a single integer - the length of the shortest transformation sequence from start to end, or 0 if none exists.

1 <= k <= 5000, 1 <= word length <= 20

Removing a word from the dictionary (or a visited-set) the MOMENT it's been used/reached is important to prevent the BFS from ever revisiting it - since BFS already guarantees the shortest path, a word only ever needs to be discovered once.

Find the shortest chain of dictionary words transforming a start word into an end word, changing one letter at a time. Brute force: For each word in the chain, scan the ENTIRE dictionary checking every word for a one-letter difference - this costs O(k * word length) per step, where k is the dictionary size, potentially slow for large dictionaries. Optimised: Generating all possible ONE-LETTER-CHANGED variations of the CURRENT word directly (word length * 25 possibilities) and checking each against a HASH SET of dictionary words (O(1) lookup) is far faster than scanning the whole dictionary for matches - especially when the dictionary is much larger than the word length.

Starting from the start word, recursively try changing each letter of the current word to every other letter of the alphabet, and if the resulting word is in the dictionary, recurse further from there, exploring all such paths via backtracking until reaching the end word, tracking the shortest path length found across all explorations. This explores every possible transformation path and will eventually find the shortest one, but without tracking which words have already been visited, it can revisit the same words repeatedly through different paths, causing exponential blow-up. Time: Exponential in the worst case Space: O(k * word length) for the recursion path

Put all dictionary words into a hash set for O(1) membership checks, then run BFS directly from the start word: at each step, for the current word, try substituting each of its L positions with every one of the 26 letters, and check each resulting variation against the hash set - any match that hasn't been visited yet is a valid neighbor to enqueue. This finds the same shortest path as the graph-based approach, but instead of comparing the current word against every other word to find neighbors (O(k) per word), it generates only the L*26 possible variations and looks each up in constant time, which is much cheaper when the dictionary is large relative to word length. Time: O(k * L * 26) Space: O(k * L)

First build an explicit graph over the k dictionary words (plus the start word), adding an edge between any two words that differ in exactly one letter, determined by comparing every pair of words character by character. Once this adjacency graph is built, run a standard BFS from the start word to the end word, and the number of edges in the shortest path (plus one) gives the answer. This correctly finds the shortest transformation sequence using well-understood BFS shortest-path logic, but constructing the graph requires comparing every pair of words against each other up front, which is expensive when k and word length are large. Time: O(k^2 * L), where L is word length Space: O(k^2) for the graph edges in the worst case

1. Model this as an unweighted graph where each dictionary word is a NODE, and BFS from the start word finds the shortest transformation length directly. 2. Rather than checking every dictionary word for a one-letter difference from the current word, generate ALL words reachable by changing one letter of the current word to every other letter, then check which of THOSE are actually in the dictionary. 3. The start word counts toward the length even if it isn't itself in the dictionary; every word AFTER it in the chain must be.

Time: O(k * L²), where k is the dictionary size and L is the word length - each word generates O(L * 26) variations, each hashed and checked in O(L). Space: O(k * L), for the dictionary hash set and the BFS queue/visited tracking.

the end word missing from the dictionary (answer 0), start equal to end, k = 1, and k at its maximum of 5000 with word length up to 20 to confirm the BFS with one-letter-change generation runs efficiently.

Be ready to explain the 'generate variations, check dictionary' optimization explicitly over the naive 'compare to every dictionary word' approach - this reversal of which direction you search is the key efficiency insight for larger dictionaries.