from collections import deque
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque()
queue.append((beginWord, 1))
visited = set()
visited.add(beginWord)
while queue:
current_word, steps = queue.popleft()
if current_word == endWord:
return steps
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = current_word[:i] + c + current_word[i+1:]
if next_word in wordSet and next_word not in visited:
visited.add(next_word)
queue.append((next_word, steps + 1))
return 0
#include <string>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (wordSet.find(endWord) == wordSet.end()) return 0;
queue<pair<string, int>> q;
q.push({beginWord, 1});
unordered_set<string> visited;
visited.insert(beginWord);
while (!q.empty()) {
auto [current, steps] = q.front();
q.pop();
if (current == endWord) return steps;
for (int i = 0; i < current.size(); ++i) {
string temp = current;
for (char c = 'a'; c <= 'z'; ++c) {
temp[i] = c;
if (wordSet.count(temp) && !visited.count(temp)) {
visited.insert(temp);
q.push({temp, steps + 1});
}
}
}
}
return 0;
}
};
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
Set<String> visited = new HashSet<>();
visited.add(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(endWord)) return steps;
char[] chars = word.toCharArray();
for (int j = 0; j < chars.length; j++) {
char original = chars[j];
for (char c = 'a'; c <= 'z'; c++) {
chars[j] = c;
String next = new String(chars);
if (wordSet.contains(next) && !visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
chars[j] = original;
}
}
steps++;
}
return 0;
}
}
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
const queue = [];
queue.push([beginWord, 1]);
const visited = new Set();
visited.add(beginWord);
while (queue.length) {
const [current, steps] = queue.shift();
if (current === endWord) return steps;
for (let i = 0; i < current.length; i++) {
for (let c = 97; c <= 122; c++) {
const next = current.slice(0, i) + String.fromCharCode(c) + current.slice(i + 1);
if (wordSet.has(next) && !visited.has(next)) {
visited.add(next);
queue.push([next, steps + 1]);
}
}
}
}
return 0;
};
You are given three inputs: a beginWord, an endWord, and a wordList (an array of valid words). Your task is to transform beginWord into endWord by changing exactly one letter at a time. Each transformed word must exist in wordList, and you may not reuse the same word more than once in a transformation sequence.
Return the minimum number of transformations (including the beginWord and endWord) needed to reach endWord from beginWord. If there is no such transformation sequence, return 0.
wordList.
At first glance, the problem seems to require trying all possible sequences of word transformations, but this quickly becomes infeasible as the size of wordList grows. A brute-force approach would involve generating all possible transformation paths and checking each for validity, but this leads to an exponential number of possibilities.
To optimize, we can recognize this problem as a shortest path search in an unweighted graph: each word is a node, and an edge exists between two words if they differ by exactly one letter. The task is to find the shortest path from beginWord to endWord in this graph.
Since we are looking for the shortest transformation, Breadth-First Search (BFS) is the natural choice. BFS explores all neighbors at the current depth before moving deeper, ensuring that the first time we reach the endWord is via the shortest sequence.
We will use BFS to find the shortest transformation sequence. Here's a step-by-step breakdown:
wordList to a set: For O(1) lookup time, store all words in a set called wordSet. If endWord is not in wordSet, immediately return 0.
(beginWord, 1).
endWord, return the step count.wordSet and hasn't been visited, add it to the queue and mark it as visited.
endWord, return 0.
The BFS ensures the shortest path is found because it explores all words at a given transformation distance before moving deeper.
Let's walk through an example:
beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log","cog"]
Step 1: Start with "hit", steps = 1.
Step 2: Possible one-letter transformations: "hot" (in wordList, add to queue).
Step 3: Next, "hot", steps = 2.
Step 4: Transformations: "dot" and "lot" (both in wordList, add to queue).
Step 5: Next, "dot", steps = 3.
Step 6: Transformations: "dog" (in wordList, add to queue).
Step 7: Next, "lot", steps = 3.
Step 8: Transformations: "log" (in wordList, add to queue).
Step 9: Next, "dog", steps = 4.
Step 10: Transformations: "cog" (matches endWord, return steps + 1 = 5).
The shortest transformation sequence is: "hit" → "hot" → "dot" → "dog" → "cog", which is 5 steps.
Brute-force approach: Would generate all possible transformation sequences, leading to exponential time and space complexity, specifically O(N!) where N is the number of words.
Optimized BFS approach:
wordList. For each word, we try changing each letter (M positions), and for each position, 26 possible letters, but since we only enqueue valid words, it's bounded by total words.
The BFS ensures we do not revisit words, keeping the process efficient.
The Word Ladder problem is elegantly solved by modeling it as a shortest path problem in a graph where words are nodes and edges connect one-letter transformations. Using BFS, we guarantee the shortest transformation sequence is found efficiently. Key insights include using a set for fast lookups and a queue for BFS traversal, ensuring each word is visited at most once. This approach scales well and avoids the pitfalls of brute-force enumeration.