Problem overview
The method ladderLength receives a start word beginWord, a target word endWord and a dictionary words as a List<String>. It must find the shortest sequence of words that starts at beginWord and ends at endWord, where each step changes exactly one letter and every word after the first must be in words. It returns the number of words in that sequence, counting both ends, or 0 if no sequence exists.
All words have the same length and contain only lowercase letters. The two end words are different, and the list has no duplicates.
For beginWord = "hit", endWord = "cog" and words = ["hot", "dot", "dog", "lot", "log", "cog"], one shortest sequence is hit -> hot -> dot -> dog -> cog. It contains 5 words, so the answer is 5. Four letter changes make a five-word ladder, so the answer is the number of changes plus one. When "cog" is missing from the list, no word ladder can end there and the answer is 0.
Approach: a graph of words and a breadth-first search
Think of every word as a node, with an edge between two words that differ in exactly one position. The question then becomes: what is the length of the shortest path from beginWord to endWord in this graph? Counting nodes on the path, not edges, gives the answer the problem wants.
Shortest paths in an unweighted graph are exactly what breadth-first search (BFS) finds. BFS keeps a queue and visits the nodes in order of distance: first the start, then everything one step away, then everything two steps away, and so on. The first time it reaches a node, it has reached it by a shortest route. A depth-first search could find a ladder quickly, but nothing would make it the shortest one.
The search needs two things: a queue of words still to explore, and a record of the words already reached together with their distance from beginWord. A single Map<String, Integer> does both jobs. A word present as a key has been reached, and the value says how many words long the ladder to it is.
Trace the first example. The queue starts with hit at distance 1. Dequeuing hit finds hot one letter away, so hot gets distance 2. Dequeuing hot finds dot and lot, both at distance 3. Dequeuing dot finds dog (distance 4), and dequeuing lot finds log (distance 4). Dequeuing dog finds cog at distance 5. When cog reaches the front of the queue the loop stops, and the map holds 5 for it.
Step by step
- Create the queue. Declare a
Deque<String>and create it as anArrayDeque. It is usually faster thanLinkedListfor queue work. - Create
minDist, aHashMapfrom word to the length of the shortest sequence reaching it. The value type isInteger, since generic type arguments must be objects. - Seed the search. Add
beginWordto the queue and put it inminDistwith distance 1, since a sequence with only the start word has length 1. - Loop while the queue is not empty. Each iteration processes one word.
- Take the front word with
poll(), which removes and returns the head. - Stop at the target. If
endWord.equals(word),break. Its distance is already in the map. Compare withequals, since==on strings compares references. - Try every candidate in
wordswith an enhancedforloop. - Skip candidates that are not one change away. A count of 0 means the same word and 2 or more means too far, so test
numOfChanges(word, nextWord) != 1. - Skip words already reached. If
minDist.containsKey(nextWord), an earlier and therefore not longer ladder is recorded. - Record and enqueue new words. Put
nextWordwith distanceminDist.get(word) + 1and add it to the queue. Recording the distance when the word is queued, not when it is dequeued, stops the same word from being queued twice. - Return the answer.
minDist.getOrDefault(endWord, 0)gives the stored distance or 0 when the target was never reached. - Write
numOfChanges. Count the positions wherefirst.charAt(i)differs fromsecond.charAt(i). Abooleancannot be added to anintin Java, so the comparison is turned into a number with the ternary operator:(a != b) ? 1 : 0.
The solution in Java
class Solution {
int numOfChanges(String first, String second) {
int differences = 0;
for (int i = 0; i < first.length(); ++i) {
differences += (first.charAt(i) != second.charAt(i)) ? 1 : 0;
}
return differences;
}
public int ladderLength(String beginWord, String endWord, List<String> words) {
Deque<String> queue = new ArrayDeque<>();
Map<String, Integer> minDist = new HashMap<>();
queue.add(beginWord);
minDist.put(beginWord, 1);
while (!queue.isEmpty()) {
String word = queue.poll();
if (endWord.equals(word)) {
break;
}
for (String nextWord : words) {
if (numOfChanges(word, nextWord) != 1) {
continue;
}
if (minDist.containsKey(nextWord)) {
continue;
}
minDist.put(nextWord, minDist.get(word) + 1);
queue.add(nextWord);
}
}
return minDist.getOrDefault(endWord, 0);
}
}
Java details worth knowing:
- Imports. The code uses
List,Deque,ArrayDeque,MapandHashMap, all fromjava.util. A file of your own needsimport java.util.*;. - Unboxing.
minDist.get(word)returns anInteger. Java unboxes it automatically for the+ 1. The call can never returnnullhere, because every word in the queue was put in the map before it was queued. continueversusbreak.continueskips to the next candidate in the inner loop, andbreakleaves thewhileloop entirely, because the onlybreakis directly inside the outer loop's body.getOrDefault.HashMap.getreturnsnullfor a missing key, which would crash if unboxed to anint.getOrDefault(endWord, 0)returns the fallback instead.
Complexity
With N words of length L, each word enters the queue at most once, so the outer loop runs at most N + 1 times. Every iteration scans the whole list, and each comparison with numOfChanges costs up to L character checks. The total is O(N^2 * L) time. The map and the queue hold at most N + 1 words, so the space is O(N), not counting the input.
A faster variant avoids the scan over the whole list: for each dequeued word, try every position and every letter from a to z, and look the result up in a HashSet of the dictionary. That costs about 26 * L lookups per word, each hashing a string of length L, so roughly O(N * L^2) overall. It wins when the dictionary is large and the words are short.
Edge cases and common mistakes
- The target is not in the list. It can never be put into the map, so the method returns 0. The second example of the problem is this case.
- The start word is not in the list. That is allowed. The start is seeded by hand, so it needs no entry in
words. If the list does contain it,numOfChangesreturns 0 for the start word itself, so it is skipped as a candidate. - Counting changes instead of words. Starting the distance at 0 gives 4 instead of 5 for the first example. The answer counts words, so the start word has distance 1.
- Using
==on strings. It compares references. Two equal strings built at run time can fail the test, so useequals. - Marking a word visited too late. If the map is updated only when a word is dequeued, the same word can be queued many times by different neighbours. That wastes time and, in larger inputs, memory.
- Words of different lengths. The comparison loop would read past the end of the shorter word and throw
StringIndexOutOfBoundsException. The problem guarantees equal lengths, so no check is needed here. - Adjacent words. If the two end words differ by one letter and the target is in the list, the answer is 2. For
"hit","hot"and the list["hot"]the result is 2.
Testing
Try the first example (5), the same list without "cog" (0), and "a" to "c" with the list ["a", "b", "c"] (2, as single-letter words are always one change apart).
