Word Ladder
Problem link: https://leetcode.com/problems/word-ladder/
Problem Statement
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord.
Rules:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
- Return 0 if there is no such transformation sequence.
Input
Two strings (beginWord, endWord) and a List of strings (wordList).
Output
An integer representing the length of the shortest path (total number of words).
Example
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog" contains 5 words.
Explanation
We start at 'hit'. In one step, we can only reach 'hot'. From 'hot', we can reach 'dot' and 'lot'. We continue layer by layer until we find 'cog'.
Brute Force
Intuition
Try every possible permutation of letters for each position in the word to find neighbors, and use recursion (DFS) to find the path.
Approach
- Use DFS to explore all paths.
- Keep track of the minimum path found.
- This is extremely slow because it explores many redundant and long paths.
Optimal Solution
Intuition
Since we need the shortest path in an unweighted graph, BFS is the most efficient choice. We process words layer by layer based on their distance from the start.
Approach
- Add
beginWordto a Queue and set distance to 1. - Convert
wordListto a Set for O(1) lookups. - While queue is not empty:
- For each word in the queue, try changing each character from 'a' to 'z'.
- If the new word is in the
wordListset:- If it's the
endWord, return current distance + 1. - Otherwise, add it to the queue and remove it from the set (to mark as visited).
- If it's the
- If queue becomes empty, return 0.
Code (Java)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curr = queue.poll();
char[] chars = curr.toCharArray();
for (int j = 0; j < chars.length; j++) {
char original = chars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[j] = c;
String next = String.valueOf(chars);
if (next.equals(endWord)) return level + 1;
if (set.contains(next)) {
queue.add(next);
set.remove(next);
}
}
chars[j] = original;
}
}
level++;
}
return 0;
}
}
Complexity Analysis
N is the number of words, L is the length of each word. We iterate through N words, and for each, we change L characters and perform string operations which take O(L).
Quick Revision (Brute Force)
- DFS explores all paths
- Inefficient for shortest path
Quick Revision (Optimal)
- BFS for shortest path
- Use a Set for O(1) word lookup
- Remove word from set to mark as visited
- Time: O(N * L^2), Space: O(N * L)