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 the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Examples:
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.Solution in Python:
To solve the problem of finding the shortest transformation sequence from beginWord to endWord using a dictionary wordList, we can use the Breadth-First Search (BFS) algorithm. BFS is suitable for this problem because it explores all possible transformations level by level, ensuring that the shortest path is found.
Python
from collections import deque, defaultdict
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# If the endWord is not in the wordList, there is no possible transformation
if endWord not in wordList:
return 0
# Add beginWord to the wordList to ensure it is considered in transformations
wordList.append(beginWord)
# Create a dictionary to store all possible generic states
# For example, for word "hit", we would store "*it", "h*t", "hi*"
word_length = len(beginWord)
all_combo_dict = defaultdict(list)
for word in wordList:
for i in range(word_length):
generic_word = word[:i] + "*" + word[i+1:]
all_combo_dict[generic_word].append(word)
# BFS queue initialization
queue = deque([(beginWord, 1)]) # (current_word, level)
visited = set() # To keep track of visited words
visited.add(beginWord)
# BFS loop
while queue:
current_word, level = queue.popleft()
# Generate all possible states for the current word
for i in range(word_length):
generic_word = current_word[:i] + "*" + current_word[i+1:]
# Get all words that match this generic state
for word in all_combo_dict[generic_word]:
# If we find the endWord, return the level + 1
if word == endWord:
return level + 1
# If the word has not been visited, add it to the queue
if word not in visited:
visited.add(word)
queue.append((word, level + 1))
# Clear the generic state list to save memory
all_combo_dict[generic_word] = []
# If we exhaust the queue and do not find the endWord, return 0
return 0Explanation:
- Check if
endWordis inwordList:- If
endWordis not in the word list, return 0 immediately since no transformation is possible.
- If
- Preprocess the
wordList:- For each word, generate all possible generic states by replacing each letter with
*. This helps in finding all possible transformations efficiently.
- For each word, generate all possible generic states by replacing each letter with
- Initialize BFS:
- Use a queue initialized with the
beginWordand a level counter starting at 1. - Use a set to keep track of visited words to avoid cycles.
- Use a queue initialized with the
- Perform BFS:
- For each word, generate all possible generic states.
- Check all words that match these generic states:
- If a match is
endWord, return the current level plus one. - If a match has not been visited, add it to the queue and mark it as visited.
- If a match is
- Return 0 if no transformation is found:
- If the queue is exhausted without finding the
endWord, return 0.
- If the queue is exhausted without finding the
This solution ensures that the shortest transformation sequence is found using BFS and avoids unnecessary computations by marking words as visited and clearing generic state lists once processed.
Solution in Javascript:
JavaScript
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
// If the endWord is not in the wordList, there is no possible transformation
if (!wordList.includes(endWord)) {
return 0;
}
// Add beginWord to the wordList to ensure it is considered in transformations
wordList.push(beginWord);
// Create a dictionary to store all possible generic states
// For example, for word "hit", we would store "*it", "h*t", "hi*"
let wordLength = beginWord.length;
let allComboDict = {};
wordList.forEach(word => {
for (let i = 0; i < wordLength; i++) {
let genericWord = word.substring(0, i) + "*" + word.substring(i + 1);
if (!allComboDict[genericWord]) {
allComboDict[genericWord] = [];
}
allComboDict[genericWord].push(word);
}
});
// BFS queue initialization
let queue = [[beginWord, 1]]; // [current_word, level]
let visited = new Set(); // To keep track of visited words
visited.add(beginWord);
// BFS loop
while (queue.length > 0) {
let [currentWord, level] = queue.shift();
// Generate all possible states for the current word
for (let i = 0; i < wordLength; i++) {
let genericWord = currentWord.substring(0, i) + "*" + currentWord.substring(i + 1);
// Get all words that match this generic state
if (allComboDict[genericWord]) {
for (let word of allComboDict[genericWord]) {
// If we find the endWord, return the level + 1
if (word === endWord) {
return level + 1;
}
// If the word has not been visited, add it to the queue
if (!visited.has(word)) {
visited.add(word);
queue.push([word, level + 1]);
}
}
// Clear the generic state list to save memory
allComboDict[genericWord] = [];
}
}
}
// If we exhaust the queue and do not find the endWord, return 0
return 0;
};Solution in Java:
Java
import java.util.*;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// If the endWord is not in the wordList, there is no possible transformation
if (!wordList.contains(endWord)) {
return 0;
}
// Add beginWord to the wordList to ensure it is considered in transformations
wordList.add(beginWord);
// Create a map to store all possible generic states
// For example, for word "hit", we would store "*it", "h*t", "hi*"
int wordLength = beginWord.length();
Map<String, List<String>> allComboDict = new HashMap<>();
for (String word : wordList) {
for (int i = 0; i < wordLength; i++) {
String genericWord = word.substring(0, i) + "*" + word.substring(i + 1);
if (!allComboDict.containsKey(genericWord)) {
allComboDict.put(genericWord, new ArrayList<>());
}
allComboDict.get(genericWord).add(word);
}
}
// BFS queue initialization
Queue<Pair<String, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>(beginWord, 1));
Set<String> visited = new HashSet<>();
visited.add(beginWord);
// BFS loop
while (!queue.isEmpty()) {
Pair<String, Integer> node = queue.remove();
String currentWord = node.getKey();
int level = node.getValue();
// Generate all possible states for the current word
for (int i = 0; i < wordLength; i++) {
String genericWord = currentWord.substring(0, i) + "*" + currentWord.substring(i + 1);
// Get all words that match this generic state
List<String> adjacentWords = allComboDict.getOrDefault(genericWord, new ArrayList<>());
for (String word : adjacentWords) {
// If we find the endWord, return the level + 1
if (word.equals(endWord)) {
return level + 1;
}
// If the word has not been visited, add it to the queue
if (!visited.contains(word)) {
visited.add(word);
queue.add(new Pair<>(word, level + 1));
}
}
// Clear the generic state list to save memory
allComboDict.put(genericWord, new ArrayList<>());
}
}
// If we exhaust the queue and do not find the endWord, return 0
return 0;
}
// Helper class to hold pairs of (word, level)
private class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
// If the endWord is not in the wordList, there is no possible transformation
if (!wordList.Contains(endWord)) {
return 0;
}
// Add beginWord to the wordList to ensure it is considered in transformations
wordList.Add(beginWord);
// Create a dictionary to store all possible generic states
// For example, for word "hit", we would store "*it", "h*t", "hi*"
int wordLength = beginWord.Length;
var allComboDict = new Dictionary<string, List<string>>();
foreach (string word in wordList) {
for (int i = 0; i < wordLength; i++) {
string genericWord = word.Substring(0, i) + "*" + word.Substring(i + 1);
if (!allComboDict.ContainsKey(genericWord)) {
allComboDict[genericWord] = new List<string>();
}
allComboDict[genericWord].Add(word);
}
}
// BFS queue initialization
var queue = new Queue<KeyValuePair<string, int>>();
queue.Enqueue(new KeyValuePair<string, int>(beginWord, 1));
var visited = new HashSet<string>(); // To keep track of visited words
visited.Add(beginWord);
// BFS loop
while (queue.Count > 0) {
var node = queue.Dequeue();
string currentWord = node.Key;
int level = node.Value;
// Generate all possible states for the current word
for (int i = 0; i < wordLength; i++) {
string genericWord = currentWord.Substring(0, i) + "*" + currentWord.Substring(i + 1);
// Get all words that match this generic state
if (allComboDict.ContainsKey(genericWord)) {
foreach (string word in allComboDict[genericWord]) {
// If we find the endWord, return the level + 1
if (word == endWord) {
return level + 1;
}
// If the word has not been visited, add it to the queue
if (!visited.Contains(word)) {
visited.Add(word);
queue.Enqueue(new KeyValuePair<string, int>(word, level + 1));
}
}
// Clear the generic state list to save memory
allComboDict[genericWord] = new List<string>();
}
}
}
// If we exhaust the queue and do not find the endWord, return 0
return 0;
}
}