You are given two words beginWord and endWord of the same length and a dictionary wordList. In one step you may change exactly one letter, and every intermediate word (and endWord) must be in wordList. Return the number of words in the shortest transformation sequence from beginWord to endWord, counting both ends, or 0 if no sequence exists.
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- All words are lowercase English letters
- beginWord != endWord
- Words in wordList are unique
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force compares every pair of words to build the graph, which costs O(N^2 * L) for N words of length L, and then runs BFS. The graph is unweighted, so BFS gives the shortest path in steps. The trick is to avoid the pairwise comparison: from a word, generate all 26 * L one-letter variations and check each in a hash set. Deleting a word from the set the moment it is enqueued doubles as the visited marker, so each word is processed once.
Algorithm
- Put
wordListinto a hash set. IfendWordis not in it, return 0. - Start BFS from
beginWordwith level 1. - For each word in the current level, try replacing every position with every letter
atoz. - If the new word equals
endWord, return level + 1. If it is in the set, remove it and enqueue it. - After finishing a level, increase the level. If the queue empties, return 0.
O(N * L * 26)Space: O(N * L)beginWord and endWord, always growing the smaller frontier. It explores far fewer words on big dictionaries.class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: words = set(wordList) if endWord not in words: return 0 words.discard(beginWord) q = deque([beginWord]) level = 1 letters = 'abcdefghijklmnopqrstuvwxyz' while q: for _ in range(len(q)): w = q.popleft() for p in range(len(w)): for c in letters: if c == w[p]: continue nxt = w[:p] + c + w[p + 1:] if nxt == endWord: return level + 1 if nxt in words: words.remove(nxt) # mark visited q.append(nxt) level += 1 return 0