LeetCode 127 · Hard · Graphs

Word Ladder

Change beginWord into endWord one letter at a time, where every word along the way must be in wordList. Return the number of words in the shortest such ladder, counting both ends, or 0 if there is none.

O(n·m²)time, m = word length
O(n·m²)space
BFSover wildcard patterns

lowercase words of one length, 1–5 letters · wordList 1–9 distinct words · beginWord ≠ endWord

bucket nei.get("pattern") · blue = new, faded = already visited

Queue front at the left · blue = this level, green = next level

public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (!wordList.contains(endWord)) { return 0; } Map<String, List<String>> nei = new HashMap<>(); wordList.add(beginWord); for (String word : wordList) { for (int j = 0; j < word.length(); j++) { String pattern = word.substring(0, j) + "*" + word.substring(j + 1); nei.computeIfAbsent(pattern, k -> new ArrayList<>()) .add(word); } } Set<String> visit = new HashSet<>(); visit.add(beginWord); Queue<String> q = new ArrayDeque<>(); q.offer(beginWord); int res = 1; while (!q.isEmpty()) { int size = q.size(); for (int i = 0; i < size; i++) { // one level String word = q.poll(); if (word.equals(endWord)) { return res; } for (int j = 0; j < word.length(); j++) { String pattern = word.substring(0, j) + "*" + word.substring(j + 1); for (String neiWord : nei.get(pattern)) { if (!visit.contains(neiWord)) { visit.add(neiWord); q.offer(neiWord); } } } } res++; } return 0;}
res
—
word
—
pattern
—
visit.size()
0
q.size()
0

Why it works

  1. Brute force compares every pair of words letter by letter to build the graph: O(n²·m). With thousands of words that pairwise step dominates.
  2. BFS finds the shortest ladder. Words are explored level by level, so the first time endWord is popped, res is the fewest words needed. visit keeps a word from entering the queue twice.
  3. Patterns replace pairwise checks. Two words differ in one letter exactly when they share a pattern like h*t. Each word has m patterns and building each costs O(m), so the buckets take O(n·m²) to build and the BFS reads each word's buckets once.
  4. Pitfall: mark a word visited when it is queued, not when it is popped, or a word reachable from two words on the same level is queued twice. And check wordList.contains(endWord) first: without it there is no ladder at all. Also, wordList.add(beginWord) changes the caller's list, so it needs a mutable list: Arrays.asList would throw UnsupportedOperationException.
  5. Related: Word Ladder II (126) returns every shortest ladder by recording parents level by level; bidirectional BFS from both ends meets in the middle and explores far fewer words.