Problem Description
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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
Examples
Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] Explanation: There are 2 shortest transformation sequences: "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog" Example 2: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Python Solution
from collections import defaultdict, deque
def findLadders(beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
# Create word set for quick lookup
word_set = set(wordList)
if endWord not in word_set:
return []
# Remove beginWord from word_set if it exists
if beginWord in word_set:
word_set.remove(beginWord)
# Create a dictionary to store neighbors
neighbors = defaultdict(list)
# Build the neighbors dictionary
def build_neighbors():
for word in [beginWord] + list(word_set):
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
neighbors[pattern].append(word)
build_neighbors()
# BFS to find shortest paths
level = {beginWord: [[beginWord]]}
while level and endWord not in level:
next_level = defaultdict(list)
for word in level:
for i in range(len(word)):
pattern = word[:i] + '*' + word[i+1:]
for nei in neighbors[pattern]:
if nei in word_set:
for path in level[word]:
next_level[nei].append(path + [nei])
# Remove visited words to prevent cycles
word_set -= set(next_level.keys())
level = next_level
return level.get(endWord, [])Java Solution
class Solution {
public List> findLadders(String beginWord, String endWord, List wordList) {
Set dict = new HashSet<>(wordList);
List> res = new ArrayList<>();
if (!dict.contains(endWord)) {
return res;
}
// Remove beginWord from dict if it exists
dict.remove(beginWord);
// Level by level BFS
Map>> level = new HashMap<>();
level.put(beginWord, Arrays.asList(Arrays.asList(beginWord)));
while (!level.isEmpty() && !level.containsKey(endWord)) {
Map>> nextLevel = new HashMap<>();
for (String word : level.keySet()) {
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String newWord = new String(chars);
if (dict.contains(newWord)) {
for (List path : level.get(word)) {
List newPath = new ArrayList<>(path);
newPath.add(newWord);
nextLevel.computeIfAbsent(newWord, k -> new ArrayList<>())
.add(newPath);
}
}
}
chars[i] = original;
}
}
// Remove visited words
dict.removeAll(nextLevel.keySet());
level = nextLevel;
}
return level.getOrDefault(endWord, res);
}
} C++ Solution
class Solution {
public:
vector> findLadders(string beginWord, string endWord, vector& wordList) {
unordered_set dict(wordList.begin(), wordList.end());
vector> res;
if (!dict.count(endWord)) {
return res;
}
// Remove beginWord from dict if it exists
dict.erase(beginWord);
// Level by level BFS
unordered_map>> level;
level[beginWord] = {{beginWord}};
while (!level.empty() && !level.count(endWord)) {
unordered_map>> nextLevel;
for (const auto& [word, paths] : level) {
string curr = word;
for (int i = 0; i < curr.length(); i++) {
char original = curr[i];
for (char c = 'a'; c <= 'z'; c++) {
curr[i] = c;
if (dict.count(curr)) {
for (const auto& path : paths) {
vector newPath = path;
newPath.push_back(curr);
nextLevel[curr].push_back(newPath);
}
}
}
curr[i] = original;
}
}
// Remove visited words
for (const auto& [word, _] : nextLevel) {
dict.erase(word);
}
level = nextLevel;
}
return level.count(endWord) ? level[endWord] : res;
}
}; JavaScript Solution
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
var findLadders = function(beginWord, endWord, wordList) {
const dict = new Set(wordList);
if (!dict.has(endWord)) {
return [];
}
// Remove beginWord from dict if it exists
dict.delete(beginWord);
// Level by level BFS
let level = new Map();
level.set(beginWord, [[beginWord]]);
while (level.size > 0 && !level.has(endWord)) {
const nextLevel = new Map();
for (const [word, paths] of level) {
const chars = word.split('');
for (let i = 0; i < chars.length; i++) {
const original = chars[i];
for (let c = 97; c <= 122; c++) { // ASCII 'a' to 'z'
chars[i] = String.fromCharCode(c);
const newWord = chars.join('');
if (dict.has(newWord)) {
for (const path of paths) {
const newPath = [...path, newWord];
if (!nextLevel.has(newWord)) {
nextLevel.set(newWord, []);
}
nextLevel.get(newWord).push(newPath);
}
}
}
chars[i] = original;
}
}
// Remove visited words
for (const word of nextLevel.keys()) {
dict.delete(word);
}
level = nextLevel;
}
return level.has(endWord) ? level.get(endWord) : [];
};C# Solution
public class Solution {
public IList> FindLadders(string beginWord, string endWord, IList wordList) {
HashSet dict = new HashSet(wordList);
var result = new List>();
if (!dict.Contains(endWord)) {
return result;
}
// Remove beginWord from dict if it exists
dict.Remove(beginWord);
// Level by level BFS
var level = new Dictionary>>();
level[beginWord] = new List> { new List { beginWord } };
while (level.Count > 0 && !level.ContainsKey(endWord)) {
var nextLevel = new Dictionary>>();
foreach (var word in level.Keys) {
var chars = word.ToCharArray();
for (int i = 0; i < chars.Length; i++) {
var original = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
var newWord = new string(chars);
if (dict.Contains(newWord)) {
foreach (var path in level[word]) {
var newPath = new List(path);
newPath.Add(newWord);
if (!nextLevel.ContainsKey(newWord)) {
nextLevel[newWord] = new List>();
}
nextLevel[newWord].Add(newPath);
}
}
}
chars[i] = original;
}
}
// Remove visited words
foreach (var word in nextLevel.Keys) {
dict.Remove(word);
}
level = nextLevel;
}
return level.ContainsKey(endWord) ? level[endWord] : result;
}
} Complexity Analysis
- Time Complexity: O(N × 26 × L × D) where N is the length of each word, L is the length of wordList, and D is the maximum depth of transformation
- Space Complexity: O(N × L × D) to store all possible paths
Solution Explanation
This solution uses a level-by-level BFS approach:
- Key concept:
- Level-wise BFS
- Path tracking
- Word transformation
- Algorithm steps:
- Build word set
- Track paths
- Transform words
- Find shortest paths
Key points:
- Avoid cycles
- Track all paths
- Level-wise search
- Efficient word generation