Word Ladder II
Hard · Graphs · Hash Table · String · Backtracking · Breadth-First Search
Problem
A transformation sequence from beginWord to endWord is a list of words that starts with beginWord, ends with endWord, changes exactly one letter from each word to the next, and uses only words from wordList after beginWord (beginWord itself need not be in the list).
Return every shortest transformation sequence, each as a list of words. The sequences may be in any order. If there is none, return an empty list.
Examples
Input: beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","word","worm"] Output: [["cold","cord","word","worm","warm"],["cold","cord","card","ward","warm"],["cold","cord","word","ward","warm"]]
Three different five-word routes are all shortest.
Input: beginWord = "cat", endWord = "dog", wordList = ["cot","cog"] Output: []
"dog" is not in the list, so no sequence exists.
Input: beginWord = "ab", endWord = "cd", wordList = ["ad","cb","cd"] Output: [["ab","ad","cd"],["ab","cb","cd"]]
Change the first letter first or the second letter first.
Constraints
- 1 <= len(beginWord) <= 5
- len(endWord) == len(beginWord)
- 1 <= len(wordList) <= 500
- len(wordList[i]) == len(beginWord)
- all words are lowercase letters
- beginWord != endWord
- the words in wordList are different
- there are at most 10^5 shortest sequences
Approaches
- Baseline: BFS over whole paths — time O(P · N · L), space O(P · L)
Follow-up
If you only needed how many shortest sequences there are, you could add counts level by level instead of listing paths, which stays fast even when there are billions: the first use case below. Searching from both ends at once also cuts down the levels explored on large dictionaries.
Related problems
Start free on Cariara · Coding problems · System design studio
