DSA problem
Word Ladder
Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
A transformation sequence is a list of words s_0 = beginWord, s_1, ..., s_k = endWord such that every adjacent pair s_i, s_{i+1} differs in exactly one letter and every s_i for i >= 1 is in wordList. The number of words in the sequence equals k + 1.
The straightforward modelling builds a graph where each dictionary word is a node and two nodes are connected if they differ in exactly one letter, then BFS from beginWord. But naively comparing every pair of words to build edges costs O(N^2 * L) where N is the dictionary size and L the word length — too slow for the constraints.
The classic optimisation is the wildcard pattern map. For every word, generate L patterns by replacing each character in turn with * (e.g. "hit" -> "*it", "h*t", "hi*"). Words sharing a pattern differ in exactly one letter at that position, so BFS can use the patterns to find neighbours in O(L) per word instead of scanning the whole dictionary. Total time becomes O(N * L^2) and space O(N * L^2).
BFS proceeds level by level from beginWord. When endWord is dequeued, the current level + 1 is the answer (sequence length is hops + 1). Mark words visited at enqueue time to avoid revisits and erase exhausted patterns from the map to avoid redundant work.
Examples
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]5beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]0beginWord = "a", endWord = "c", wordList = ["a","b","c"]2Constraints
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord, endWord, and wordList[i] consist of lowercase English letters.
- beginWord != endWord
- All the words in wordList are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.