Word Ladder
Transform a start word into an end word by changing one letter at a time. Every word after the start must be in the dictionary. Find the shortest sequence length, including start and end.
Work through the cases
3 examplesInput notation
Start word on line 1; end word on line 2; space-separated dictionary on line 3. All words have equal length; start and end differ.Expected result
The shortest length, or 0 if impossible.Case 1
Input
hit cog hot dot dog lot log cog
Expected output
5
Case 2
Input
hit cog hot dot dog
Expected output
0
Case 3
Input
a c a b c
Expected output
2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Find the shortest transformation; each step changes one letter and must stay in the word list. With up to 5000 words of length 10, enumerating paths is impossible. Unweighted shortest paths are BFS: try 26 letters at each position, enqueue hits, and remove them from the set so they are not visited twice.
BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.
Bidirectional BFS is a common optimization method for BFS, with the main implementation ideas as follows:
1. Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively. 2. Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps). 3. During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found. 4. If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.
python while q1 and q2: if len(q1) <= len(q2): # Prioritize the queue with fewer elements for expansion extend(m1, m2, q1) else: extend(m2, m1, q2)
def extend(m1, m2, q): # New round of expansion for _ in range(len(q)): p = q.popleft() step = m1[p] for t in next(p): if t in m1: # Already visited before continue if t in m2: # The other direction has been searched, indicating that a shortest path has been found return step + 1 + m2[t] q.append(t) m1[t] = step + 1
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
int ans = 1;
while (!q.isEmpty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
String s = q.poll();
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
if (!words.contains(t)) {
continue;
}
if (endWord.equals(t)) {
return ans;
}
q.offer(t);
words.remove(t);
}
chars[j] = ch;
}
}
}
return 0;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.