Word Ladder
You're given two words, beginWord and endWord, and a list of words wordList. A transformation sequence starts at beginWord and changes exactly one letter per step, and every word after beginWord must be in wordList (beginWord itself doesn't have to be). Return the number of words in the shortest sequence that ends at endWord, counting both beginWord and endWord. If no such sequence exists, including when endWord isn't in wordList, return 0.
Examples
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] returns 5
"hit" -> "hot" -> "dot" -> "dog" -> "cog" uses 5 words. "hit" can only step to "hot", so a 4-word sequence would need one word between "hot" and "cog", such as "hog" or "cot", and neither is in wordList.
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] returns 0
"cog" is not in wordList, so no sequence can end there and the answer is 0.
Constraints
- 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.
Hints
Picture every word as a point, with a link between two words that differ in exactly one letter. What does the shortest sequence become in that picture?
It's a shortest path in an unweighted graph, so use breadth-first search. Find neighbors by swapping each position to each of the 26 letters and checking a set of words.
Put wordList in a set and return 0 if endWord is missing. BFS from beginWord with length = 1. Pop each word; if it's endWord, return length. Otherwise, for every one-letter change found in the set, remove it and enqueue it. Add 1 to length after each level, and return 0 if the queue empties.
Drill This: Your Approach First
Approach
Treat each word as a node with an edge to every word one letter away. The shortest sequence is then a shortest path in an unweighted graph, which breadth-first search finds level by level from beginWord. Instead of comparing all pairs, generate neighbors by trying all 26 letters at each position and keeping those still in the word set, removing each word when it's enqueued. With n words of length L, each word yields 26 * L candidates that each cost O(L) to build and hash.
Time
O(n * L^2)
Space
O(n * L)
Pitfall
Solutions
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
Deque<String> queue = new ArrayDeque<>();
queue.offer(beginWord);
words.remove(beginWord);
int length = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
String word = queue.poll();
if (word.equals(endWord)) return length;
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[i] = c;
String next = new String(chars);
if (words.remove(next)) queue.offer(next);
}
chars[i] = original;
}
}
length++;
}
return 0;
}
}from collections import deque
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
queue = deque([beginWord])
words.discard(beginWord)
length = 1
while queue:
for _ in range(len(queue)):
word = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
nxt = word[:i] + ch + word[i + 1:]
if nxt in words:
words.remove(nxt)
queue.append(nxt)
length += 1
return 0