Practice › Graphs
Word Ladder
Hard · Graphs · Asked at Amazon, Google, Meta, Microsoft, LinkedIn
Transform begin into end by changing one letter at a time, where every intermediate word (and end) must be in the dictionary. Print the number of words in the shortest transformation sequence (counting begin and end), or 0 if it is impossible.
Input
First line: begin end. Second line: n. Third line: the n dictionary words. All words have the same length and are lowercase.
Output
The length of the shortest sequence, or 0.
Constraints
- 1 ≤ word length ≤ 10
- 1 ≤ n ≤ 5000
BFS over words. To find neighbours, try changing each position to each of the 26 letters and check a hash set.
Example 1
Input
hit cog 6 hot dot dog lot log cog
Output
5
Example 2
Input
hit cog 5 hot dot dog lot log
Output
0
Hints
- Every word is a node; words differing in exactly one letter are connected. You want the shortest path — BFS.
- Do not compare every pair of words. For a word, generate all variants with one letter changed (26 · length) and look them up in a hash set.
Approach
If end is not in the dictionary, print 0. BFS from begin with distance 1. For the word at the front of the queue, try every position and every letter; each variant that is in the dictionary and unvisited gets distance + 1 and is queued (remove it from the set to mark it visited). The first time end is popped, its distance is the number of words in the shortest sequence. If the queue empties, print 0.
Complexity: O(n · L · 26) time · O(n · L) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string b, e;
int n;
cin >> b >> e >> n;
unordered_set<string> dict;
for (int i = 0; i < n; i++) {
string w;
cin >> w;
dict.insert(w);
}
if (!dict.count(e)) {
cout << 0 << "\n";
return 0;
}
queue<pair<string, int>> q;
q.push({b, 1});
dict.erase(b);
while (!q.empty()) {
string w = q.front().first;
int d = q.front().second;
q.pop();
if (w == e) {
cout << d << "\n";
return 0;
}
for (size_t p = 0; p < w.size(); p++) {
char orig = w[p];
for (char c = 'a'; c <= 'z'; c++) {
w[p] = c;
if (dict.count(w)) {
dict.erase(w);
q.push({w, d + 1});
}
}
w[p] = orig;
}
}
cout << 0 << "\n";
return 0;
}Python solution
import sys
from collections import deque
data = sys.stdin.read().split()
b, e, n = data[0], data[1], int(data[2])
words = set(data[3 : 3 + n])
ans = 0
if e in words:
words.discard(b)
q = deque([(b, 1)])
while q:
w, d = q.popleft()
if w == e:
ans = d
break
for p in range(len(w)):
for c in "abcdefghijklmnopqrstuvwxyz":
x = w[:p] + c + w[p + 1 :]
if x in words:
words.discard(x)
q.append((x, d + 1))
print(ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String b = sc.next(), e = sc.next();
int n = sc.nextInt();
Set<String> dict = new HashSet<>();
for (int i = 0; i < n; i++) dict.add(sc.next());
if (!dict.contains(e)) {
System.out.println(0);
return;
}
dict.remove(b);
ArrayDeque<String> q = new ArrayDeque<>();
Map<String, Integer> dist = new HashMap<>();
q.add(b);
dist.put(b, 1);
while (!q.isEmpty()) {
String w = q.poll();
int d = dist.get(w);
if (w.equals(e)) {
System.out.println(d);
return;
}
char[] cs = w.toCharArray();
for (int p = 0; p < cs.length; p++) {
char orig = cs[p];
for (char c = 'a'; c <= 'z'; c++) {
cs[p] = c;
String x = new String(cs);
if (dict.remove(x)) {
dist.put(x, d + 1);
q.add(x);
}
}
cs[p] = orig;
}
}
System.out.println(0);
}
}