Word Ladder
Hard · Graphs · Hash Table · String · Breadth-First Search
Problem
You are given two words, beginWord and endWord, and a dictionary wordList. A ladder goes from beginWord to endWord one word at a time, where each step changes exactly one letter, and every word after beginWord must be in wordList. beginWord itself does not have to be in the list.
Return the number of words in the shortest ladder, counting both ends. If there is no ladder (including when endWord is not in wordList), return 0.
No graph is given, but there is one: the words are the nodes, and two words are joined when they differ in one position. The question is a shortest path in that unweighted graph.
Examples
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5
One shortest ladder is hit → hot → dot → dog → cog, five words.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0
cog is not in the dictionary, so no ladder can end there.
Constraints
- 1 <= len(beginWord) <= 10
- len(endWord) == len(beginWord), and every word in wordList has that length too
- 1 <= len(wordList) <= 5000
- all words are lowercase English letters
- beginWord != endWord
- the words in wordList are distinct
Approaches
- BFS comparing every pair of words — time O(N² · L), space O(N)
Follow-up
Can you search from both ends at once, always expanding the smaller frontier? How much does that save when the ladder is long and each word has many neighbors?
Related problems
Start free on Cariara · Coding problems · System design studio
