Word Ladder
The drill: Transform a start word into a target word one letter swap at a time, where every intermediate word must exist in a given dictionary — find the fewest words needed for such a chain, or report that none exists.
A start word and an end word share the same length, and a dictionary of same-length words sits between them. The drill is to hop from the start to the end one word at a time, changing exactly one letter per hop.
Every word visited along the way — except the start — has to already exist in that dictionary. The start word itself is free to be outside it, but every hop after that lands only on dictionary entries.
The task is the length of the shortest such chain, counting the start word as the first entry and the end word as the last. If no sequence of one-letter hops can reach the end word through the dictionary, the chain doesn't exist.
- words in the chain all share the same fixed length
- dictionary can hold up to a few thousand words, lowercase letters only
- each hop changes exactly one letter and must land in the dictionary
- start word may sit outside the dictionary; the target must be inside it
- chain length counts both the start and the end word
HINT 1 THE NUDGE
Treat every word in the dictionary as a node, and draw an edge between two words whenever they differ in exactly one letter. The question is now shortest path in that graph — and shortest path in an unweighted graph has one classic tool.
HINT 2 THE STRUCTURE
You don't have to discover edges by comparing every pair of words. Swap one letter of a word for a wildcard and you get a pattern that every one-hop neighbor shares — group the whole dictionary by those patterns once, up front.
HINT 3 ONE STEP FROM THE ANSWER
Run a breadth-first search from the start word, expanding through the wildcard buckets instead of a pairwise scan. The level at which the target word first appears — counting the start word itself as level one — is the answer; an empty frontier with no target found means no chain exists.
Bucket every word by its wildcard pattern, so 'c*t' maps to cat and cot. Level-order BFS from cat finds the shortest ladder to dog.
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
length = len(beginWord)
buckets = collections.defaultdict(list)
for word in word_set:
for i in range(length):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = collections.deque([(beginWord, 1)])
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(length):
pattern = word[:i] + "*" + word[i + 1:]
for neighbor in buckets[pattern]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, steps + 1))
return 0class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList)
if endWord not in word_set:
return 0
def one_letter_apart(a: str, b: str) -> bool:
diff = 0
for x, y in zip(a, b):
if x != y:
diff += 1
if diff > 1:
return False
return diff == 1
visited = {beginWord}
queue = collections.deque([(beginWord, 1)])
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
# rediscover every edge from scratch: walk the whole remaining dictionary
for candidate in word_set - visited:
if one_letter_apart(word, candidate):
visited.add(candidate)
queue.append((candidate, steps + 1))
return 0class Solution {
public int ladderLength(String beginWord, String endWord, String[] wordList) {
Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
if (!wordSet.contains(endWord)) {
return 0;
}
int length = beginWord.length();
Map<String, List<String>> buckets = new HashMap<>();
for (String word : wordSet) {
for (int i = 0; i < length; i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
}
}
Set<String> visited = new HashSet<>();
visited.add(beginWord);
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
String word = queue.poll();
if (word.equals(endWord)) {
return steps;
}
for (int i = 0; i < length; i++) {
String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
for (String neighbor : buckets.getOrDefault(pattern, Collections.emptyList())) {
if (visited.add(neighbor)) {
queue.offer(neighbor);
}
}
}
}
steps++;
}
return 0;
}
}class Solution {
public int ladderLength(String beginWord, String endWord, String[] wordList) {
Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
if (!wordSet.contains(endWord)) {
return 0;
}
Set<String> visited = new HashSet<>();
visited.add(beginWord);
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int s = 0; s < size; s++) {
String word = queue.poll();
if (word.equals(endWord)) {
return steps;
}
// rediscover every edge from scratch: walk the whole remaining dictionary
for (String candidate : wordSet) {
if (!visited.contains(candidate) && oneLetterApart(word, candidate)) {
visited.add(candidate);
queue.offer(candidate);
}
}
}
steps++;
}
return 0;
}
private boolean oneLetterApart(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
diff++;
if (diff > 1) {
return false;
}
}
}
return diff == 1;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED