The problem
A ladder from beginWord to endWord is a sequence of words, each differing from the one before in exactly one letter, where every word after the first is in wordList.
Return the number of words in the shortest ladder, or 0 if there is none.
Examples
- Input
beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
- Output
5
- Input
beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log"]
- Output
0
Constraints
- 1 ≤ beginWord.length ≤ 10
endWordhas the same length;beginWord≠endWord.- 1 ≤ wordList.length ≤ 5000
- All words are lowercase and different.
The idea
Picture every word as a node, with an edge between two words one letter apart. The question is then the shortest path from beginWord to endWord, and in a graph whose edges all count the same, breadth-first search finds shortest paths.
The edges are never built. From a word, try each position with each of the 26 letters and keep the results that are in the word list — at most 26 × L lookups. Remove each word from the list when it is first reached: breadth-first reaches it first by a shortest route, so no later route can be better.
- Time
- O(N · L² · 26) — N words, each tried at L positions, each new word L letters long
- Space
- O(N · L)
Solution · every language run against every case
class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: words = set(wordList) if endWord not in words: return 0 # Breadth-first: every word reached in round k is k steps from the start, the fewest possible. frontier, steps = [beginWord], 1 words.discard(beginWord) while frontier: nxt = [] for w in frontier: if w == endWord: return steps for i in range(len(w)): for ch in "abcdefghijklmnopqrstuvwxyz": # every word one letter away cand = w[:i] + ch + w[i + 1 :] if cand in words: words.remove(cand) # reached now, by the shortest route nxt.append(cand) frontier, steps = nxt, steps + 1 return 0