Log inSign up
hardLeetCodeNot Started

Word Ladder

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: - Every adjacent pair of words differs by a single letter. - Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. - sk == endWord.

Given two words, beginWord and endWord, and a dictionary wordList, return *the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists*.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are meaningful and unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model state transformation problems as unweighted graph BFS traversals.
  • Optimize neighbor generation using character mutation with HashSet lookups (O(26L)) vs. pairwise distance scans (O(N \cdot L)).
  • Implement in-place visited tracking by deleting matched words from the HashSet.
  • Implement Bidirectional BFS to reduce the search branching factor.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever transforming an initial state to a goal state via discrete single-unit valid modifications (1 character difference) and asking for the shortest sequence, use Breadth-First Search (BFS) or Bidirectional BFS.

1. DFS Exhaustive Transformation Search

Intuition

Use Depth-First Search with backtracking to explore all valid one-letter transformations from beginWord towards endWord. Track visited words to avoid infinite loops. Maintain a minimum path length; return the shortest path length found, or 0 if unreachable.

Algorithm

  1. If endWord is not in wordList, return 0.
  2. Store wordList in a set dict.
  3. Initialize visited set.
  4. Define dfs(currWord, depth):
  5. If currWord == endWord, update minLen = min(minLen, depth).
  6. For each word w in dict not in visited differing by exactly 1 letter:
  7. visited.add(w)
  8. dfs(w, depth + 1)
  9. visited.remove(w) (backtrack)
  10. Return minLen.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6#include <climits>
7
8bool differsByOne(const std::string& a, const std::string& b) {
9 int diff = 0;
10 for (int i = 0; i < (int)a.size(); ++i) {
11 if (a[i] != b[i]) {
12 if (++diff > 1) return false;
13 }
14 }
15 return diff == 1;
16}
17
18void dfs(const std::string& curr, const std::string& target, int depth,
19 const std::vector<std::string>& words, std::vector<bool>& visited, int& minDepth) {
20 if (depth >= minDepth) return;
21 if (curr == target) {
22 minDepth = depth;
23 return;
24 }
25
26 for (int i = 0; i < (int)words.size(); ++i) {
27 if (!visited[i] && differsByOne(curr, words[i])) {
28 visited[i] = true;
29 dfs(words[i], target, depth + 1, words, visited, minDepth);
30 visited[i] = false;
31 }
32 }
33}
34
35int ladderLengthDFS(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
36 int minDepth = INT_MAX;
37 std::vector<bool> visited(wordList.size(), false);
38 dfs(beginWord, endWord, 1, wordList, visited, minDepth);
39 return minDepth == INT_MAX ? 0 : minDepth;
40}
41
42int main() {
43 std::vector<std::string> wordList = {"hot","dot","dog","lot","log","cog"};
44 std::cout << "Word Ladder (DFS): " << ladderLengthDFS("hit", "cog", wordList) << std::endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N!) worst case as all permutation paths of words are explored.
  • Space complexity: O(N) for the recursion stack and visited set.

2. Standard Breadth-First Search (BFS)

Intuition

Because each word-to-word transformation is an unweighted step, BFS naturally explores transformations level by level. Put (beginWord, 1) into a queue. For each popped word, generate all 26 variants at each of its L positions. If a variant is in the dictionary set, remove it from the set (marking visited) and enqueue it with level + 1. The first time endWord is matched, its level is guaranteed to be minimal.

Algorithm

  1. Store all words from wordList into a HashSet wordSet.
  2. If endWord is not in wordSet, return 0.
  3. Initialize queue q with (beginWord, 1).
  4. Remove beginWord from wordSet if present.
  5. While q is not empty:
  6. Pop (word, level).
  7. If word == endWord, return level.
  8. For i = 0 to word.length - 1:
  9. For char c = a to z:
  10. Create mutant = word with char at i replaced by c.
  11. If mutant is in wordSet:
  12. wordSet.erase(mutant) (mark visited)
  13. q.push((mutant, level + 1))
  14. Return 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <queue>
6
7int ladderLengthBFS(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
8 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
9 if (dict.find(endWord) == dict.end()) return 0;
10
11 std::queue<std::pair<std::string, int>> q;
12 q.push({beginWord, 1});
13 dict.erase(beginWord);
14
15 while (!q.empty()) {
16 auto [word, level] = q.front();
17 q.pop();
18
19 if (word == endWord) return level;
20
21 for (int i = 0; i < (int)word.size(); ++i) {
22 char original = word[i];
23 for (char c = 'a'; c <= 'z'; ++c) {
24 word[i] = c;
25 if (dict.find(word) != dict.end()) {
26 dict.erase(word);
27 q.push({word, level + 1});
28 }
29 }
30 word[i] = original;
31 }
32 }
33 return 0;
34}
35
36int main() {
37 std::vector<std::string> wordList = {"hot","dot","dog","lot","log","cog"};
38 std::cout << "Word Ladder (BFS): " << ladderLengthBFS("hit", "cog", wordList) << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(M^2 * N) where M is word length and N is wordList.length. There are at most N words visited, and for each word we check 26*M mutations of length M.
  • Space complexity: O(M * N) to store the dictionary set and queue.

3. Bidirectional BFS

Intuition

Instead of searching from beginWord alone (where the search frontier expands exponentially as bd), search simultaneously forward from beginWord and backward from endWord. In each iteration, expand the smaller of the two frontiers. When a mutant generated from one frontier exists in the other frontier, the search spaces meet, reducing the branching factor from O(bd) down to O(b^{d/2}).

Algorithm

  1. Store wordList in a set dict. If endWord not in dict, return 0.
  2. Initialize two sets: beginSet = {beginWord}, endSet = {endWord}.
  3. Initialize level = 1.
  4. While !beginSet.empty() && !endSet.empty():
  5. Always expand the smaller set: if beginSet.size() > endSet.size(), swap them.
  6. Create nextLevelSet.
  7. For each word in beginSet:
  8. Generate all mutations:
  9. If mutant is in endSet, return level + 1 (frontiers met!).
  10. If mutant is in dict:
  11. dict.erase(mutant)
  12. nextLevelSet.insert(mutant)
  13. beginSet = nextLevelSet
  14. level++
  15. Return 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6
7int ladderLengthBidirectional(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
8 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
9 if (dict.find(endWord) == dict.end()) return 0;
10
11 std::unordered_set<std::string> beginSet{beginWord};
12 std::unordered_set<std::string> endSet{endWord};
13 dict.erase(beginWord);
14 dict.erase(endWord);
15
16 int level = 1;
17
18 while (!beginSet.empty() && !endSet.empty()) {
19 if (beginSet.size() > endSet.size()) {
20 std::swap(beginSet, endSet);
21 }
22
23 std::unordered_set<std::string> nextSet;
24 for (std::string word : beginSet) {
25 for (int i = 0; i < (int)word.size(); ++i) {
26 char orig = word[i];
27 for (char c = 'a'; c <= 'z'; ++c) {
28 word[i] = c;
29 if (endSet.find(word) != endSet.end()) {
30 return level + 1;
31 }
32 if (dict.find(word) != dict.end()) {
33 dict.erase(word);
34 nextSet.insert(word);
35 }
36 }
37 word[i] = orig;
38 }
39 }
40 beginSet = nextSet;
41 level++;
42 }
43
44 return 0;
45}
46
47int main() {
48 std::vector<std::string> wordList = {"hot","dot","dog","lot","log","cog"};
49 std::cout << "Optimal Word Ladder (Bi-BFS): " << ladderLengthBidirectional("hit", "cog", wordList) << std::endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(M^2 * N) worst case, but practically exponentially faster (O(b^(d/2))) due to bidirectional frontier meeting.
  • Space complexity: O(M * N) for the dictionary and frontier sets.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS BacktrackingO(N!)O(N)Simple recursive trail.Exponential runtime; checks all paths rather than finding shortest directly.
2.Standard BFSO(M^2 * N)O(M * N)Finds shortest transformation sequence level by level without backtracking.Expands all branches from one side.
3.Bidirectional BFSOptimalO(M^2 * N)O(M * N)Cuts search tree depth in half, reducing exponential branching from bd to 2 * b^(d/2); significantly faster in practice.Requires synchronizing two frontier sets.

Common Pitfalls & Crucial Edge Cases

Returning the number of transitions instead of number of words.

The problem asks for the number of words in the sequence. A sequence hit -> hot -> cog has 2 transitions but 3 words; return level which starts at 1.

Comparing all N words in the dictionary on every step ($O(N^2)$).

For M <= 10 and N = 5000, mutate each character 26 times with O(1) HashSet lookups.

Crucial Edge Cases to Validate:

  • endWord not in wordList — Return 0 immediately.
  • beginWord differs from endWord by 1 letter and endWord is in wordList — Direct 1-step transformation; returns 2.
  • No possible transformation path exists — Queue empties; algorithm returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both Standard BFS and Bidirectional BFS. Show how Bidirectional BFS reduces branching complexity from bd to 2 * b^(d/2).
  2. Explain the word mutation optimization: 26 * L * O(1) hash lookup vs O(N * L) pairwise comparison.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we generate 26 * M mutated strings instead of scanning all N words in the dictionary?

2.What should be returned if endWord is not in wordList?

3.In Bidirectional BFS, why do we swap beginSet and endSet?

Back to DSA Sheet