Word Ladder
Word Ladder is a hard graphs problem solved with the bfs for shortest path pattern.
The best approach, optimal (bfs with letter substitution), runs in O(N · L² · 26) time and O(N · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs comparing every pair) up.
Problem
A transformation sequence from beginWord to endWord is a list of words that starts with beginWord, ends with endWord, and where every consecutive pair differs in exactly one letter. Every word after beginWord must come from wordList (beginWord itself does not need to be in it).
Return the number of words in the shortest such sequence, or 0 if no sequence exists.
Examples
Example 1
- Input
beginWord = "cold", endWord = "warm", wordList = ["cord","card","ward","warm","worm","word"]- Output
5- Why
- cold -> cord -> card -> ward -> warm has 5 words, and no shorter chain exists.
Example 2
- Input
beginWord = "pin", endWord = "pit", wordList = ["pit","pat"]- Output
2- Why
- One letter change turns pin into pit, so the sequence is just the two words.
Example 3
- Input
beginWord = "bake", endWord = "lime", wordList = ["bike","like","lake"]- Output
0- Why
- lime is not in the list, so it can never be reached.
Constraints
1 <= beginWord.length <= 10;endWordand every word inwordListhave the same length.1 <= wordList.length <= 5000; all words inwordListare distinct.- All words contain only lowercase English letters, and
beginWord != endWord.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS comparing every pair) | O(N² · L) | O(N) |
| Optimal (BFS with letter substitution) | O(N · L² · 26) | O(N · L) |
1Brute force (BFS comparing every pair)
O(N² · L)Each of the N words is popped once and compared with all N words, each comparison costing L.O(N)The queue and the visited array.Run BFS from beginWord. To find the neighbours of a word, scan the whole list and keep the unvisited words that differ from it in exactly one position.
- If endWord is not in the list, return 0.
- Queue beginWord with level 1; mark list words as visited when enqueued.
- Pop a word; for every unvisited list word at distance one, return level + 1 if it is endWord, else enqueue it.
- If the queue empties, return 0.
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int n = wordList.size();
if (!wordList.contains(endWord)) return 0;
boolean[] used = new boolean[n];
Queue<String> q = new ArrayDeque<>();
q.add(beginWord);
int level = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
String cur = q.poll();
for (int i = 0; i < n; i++) {
if (used[i] || !oneApart(cur, wordList.get(i))) continue;
if (wordList.get(i).equals(endWord)) return level + 1;
used[i] = true;
q.add(wordList.get(i));
}
}
level++;
}
return 0;
}
private boolean oneApart(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++)
if (a.charAt(i) != b.charAt(i) && ++diff > 1) return false;
return diff == 1;
}
}class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
n = len(wordList)
if endWord not in wordList:
return 0
used = [False] * n
q = deque([beginWord])
level = 1
while q:
for _ in range(len(q)):
cur = q.popleft()
for i in range(n):
if used[i] or not self.oneApart(cur, wordList[i]):
continue
if wordList[i] == endWord:
return level + 1
used[i] = True
q.append(wordList[i])
level += 1
return 0
def oneApart(self, 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 == 1class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0;
vector<bool> used(n, false);
queue<string> q;
q.push(beginWord);
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
string cur = q.front();
q.pop();
for (int i = 0; i < n; i++) {
if (used[i] || !oneApart(cur, wordList[i])) continue;
if (wordList[i] == endWord) return level + 1;
used[i] = true;
q.push(wordList[i]);
}
}
level++;
}
return 0;
}
private:
bool oneApart(const string& a, const string& b) {
int diff = 0;
for (int i = 0; i < (int)a.size(); i++)
if (a[i] != b[i] && ++diff > 1) return false;
return diff == 1;
}
};function ladderLength(beginWord, endWord, wordList) {
const n = wordList.length;
if (!wordList.includes(endWord)) return 0;
const used = new Array(n).fill(false);
let q = [beginWord];
let level = 1;
while (q.length > 0) {
const next = [];
for (const cur of q) {
for (let i = 0; i < n; i++) {
if (used[i] || !oneApart(cur, wordList[i])) continue;
if (wordList[i] === endWord) return level + 1;
used[i] = true;
next.push(wordList[i]);
}
}
q = next;
level++;
}
return 0;
}
function oneApart(a, b) {
let diff = 0;
for (let i = 0; i < a.length; i++)
if (a[i] !== b[i] && ++diff > 1) return false;
return diff === 1;
}2Optimal (BFS with letter substitution)
O(N · L² · 26)Each of N words produces 26 · L candidates, and building or hashing each candidate costs L.O(N · L)The set and the queue store up to N words of length L.Put the list in a hash set. For each word popped from the BFS queue, generate every word one substitution away (L positions times 26 letters) and keep only those still in the set. Removing a word from the set when it is enqueued doubles as the visited mark.
- Put all list words in a set; if endWord is missing, return 0.
- BFS level by level from beginWord, starting at level 1.
- For each position i and each letter c, form the candidate; if it equals endWord return level + 1; if it is in the set, remove it and enqueue it.
- Return 0 when the queue empties.
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> left = new HashSet<>(wordList);
if (!left.contains(endWord)) return 0;
left.remove(beginWord);
Queue<String> q = new ArrayDeque<>();
q.add(beginWord);
int level = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
char[] w = q.poll().toCharArray();
for (int i = 0; i < w.length; i++) {
char orig = w[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
w[i] = c;
String cand = new String(w);
if (cand.equals(endWord)) return level + 1;
if (left.remove(cand)) q.add(cand);
}
w[i] = orig;
}
}
level++;
}
return 0;
}
}class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
left = set(wordList)
if endWord not in left:
return 0
left.discard(beginWord)
q = deque([beginWord])
level = 1
letters = 'abcdefghijklmnopqrstuvwxyz'
while q:
for _ in range(len(q)):
w = q.popleft()
for i in range(len(w)):
for c in letters:
if c == w[i]:
continue
cand = w[:i] + c + w[i + 1:]
if cand == endWord:
return level + 1
if cand in left:
left.remove(cand)
q.append(cand)
level += 1
return 0class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> left(wordList.begin(), wordList.end());
if (!left.count(endWord)) return 0;
left.erase(beginWord);
queue<string> q;
q.push(beginWord);
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
string w = q.front();
q.pop();
for (int i = 0; i < (int)w.size(); i++) {
char orig = w[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
w[i] = c;
if (w == endWord) return level + 1;
if (left.erase(w)) q.push(w);
}
w[i] = orig;
}
}
level++;
}
return 0;
}
};function ladderLength(beginWord, endWord, wordList) {
const left = new Set(wordList);
if (!left.has(endWord)) return 0;
left.delete(beginWord);
let q = [beginWord];
let level = 1;
while (q.length > 0) {
const next = [];
for (const w of q) {
for (let i = 0; i < w.length; i++) {
for (let c = 97; c <= 122; c++) {
const ch = String.fromCharCode(c);
if (ch === w[i]) continue;
const cand = w.slice(0, i) + ch + w.slice(i + 1);
if (cand === endWord) return level + 1;
if (left.has(cand)) {
left.delete(cand);
next.push(cand);
}
}
}
}
q = next;
level++;
}
return 0;
}Edge cases to test
- endWord missing from wordList (answer 0)
- beginWord itself is in wordList
- endWord is one letter away from beginWord (answer 2)
- Words of length 1
Hints
Hint 1
Treat every word as a node and connect two words when they differ in exactly one position. You want the shortest path.
Hint 2
Shortest path in an unweighted graph means BFS, counting levels.
Hint 3
Instead of comparing a word with every other word, try all 26 letters in each position and look the result up in a hash set.
FAQ
What is the best time complexity for Word Ladder?
Optimal (BFS with letter substitution) runs in O(N · L² · 26) time and O(N · L) extra space. Each of N words produces 26 · L candidates, and building or hashing each candidate costs L.
Which pattern does Word Ladder use?
It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix.
Is there a brute force solution for Word Ladder?
Yes. Brute force (BFS comparing every pair) takes O(N² · L) time and O(N) space. Run BFS from beginWord.
Which edge cases should I test for Word Ladder?
endWord missing from wordList (answer 0); beginWord itself is in wordList; endWord is one letter away from beginWord (answer 2); Words of length 1.