Problem
Given two words and a dictionary, find the shortest transformation sequence from beginWord to endWord. Each step changes one letter and must be in the dictionary.
Example
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
hit -> hot -> dot -> dog -> cog.Solution
BFS treating each word as a node. Use wildcard pattern (e.g., “h*t”) to find neighbors efficiently.
from collections import defaultdict, deque
def ladder_length(begin, end, word_list):
if end not in word_list: return 0
L = len(begin)
patterns = defaultdict(list)
for w in word_list:
for i in range(L):
patterns[w[:i] + '*' + w[i+1:]].append(w)
visited = {begin}
q = deque([(begin, 1)])
while q:
word, steps = q.popleft()
for i in range(L):
p = word[:i] + '*' + word[i+1:]
for nei in patterns[p]:
if nei == end: return steps + 1
if nei not in visited:
visited.add(nei)
q.append((nei, steps + 1))
return 0function ladderLength(begin, end, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(end)) return 0;
let q = [[begin, 1]];
const visited = new Set([begin]);
while (q.length) {
const [word, steps] = q.shift();
if (word === end) return steps;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) {
const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (wordSet.has(next) && !visited.has(next)) {
visited.add(next);
q.push([next, steps + 1]);
}
}
}
}
return 0;
}int ladderLength(string begin, string end, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (!dict.count(end)) return 0;
queue<pair<string, int>> q;
q.push({begin, 1});
unordered_set<string> visited{begin};
while (!q.empty()) {
auto [word, steps] = q.front(); q.pop();
if (word == end) return steps;
for (int i = 0; i < word.size(); i++) {
char orig = word[i];
for (char c = 'a'; c <= 'z'; c++) {
word[i] = c;
if (dict.count(word) && !visited.count(word)) {
visited.insert(word);
q.push({word, steps + 1});
}
}
word[i] = orig;
}
}
return 0;
}public int ladderLength(String begin, String end, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(end)) return 0;
Queue<String> q = new LinkedList<>();
q.offer(begin);
Set<String> visited = new HashSet<>(); visited.add(begin);
int steps = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
String word = q.poll();
if (word.equals(end)) return steps;
char[] arr = word.toCharArray();
for (int i = 0; i < arr.length; i++) {
char orig = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
arr[i] = c;
String next = new String(arr);
if (dict.contains(next) && !visited.contains(next)) {
visited.add(next);
q.offer(next);
}
}
arr[i] = orig;
}
}
steps++;
}
return 0;
}Complexity
- Time: O(M² × N)
- Space: O(M × N)
Explanation
BFS guarantees shortest path. Try every single-letter change and see if the resulting word is in the dictionary.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?