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
si
for1 <= i <= k
is inwordList
. Note thatbeginWord
does 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.
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.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
,endWord
, andwordList[i]
consist of lowercase English letters.beginWord != endWord
- All the words in
wordList
are unique.
Java Solution
To solve this problem, you can use BFS to find the shortest transformation sequence from beginWord
to endWord
. You can maintain a queue and traverse the possible transformations, marking visited words to avoid revisiting them.
Here’s the Java solution:
import java.util.*;
public class WordLadderLength {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
return 0; // If endWord is not in wordList, return 0
}
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
int transformations = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String currentWord = queue.poll();
// Generate all possible next words by changing one letter at a time
for (int j = 0; j < currentWord.length(); j++) {
char[] charArray = currentWord.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
charArray[j] = c;
String nextWord = new String(charArray);
if (nextWord.equals(endWord)) {
return transformations + 1; // Found the endWord
}
if (wordSet.contains(nextWord) && !visited.contains(nextWord)) {
visited.add(nextWord);
queue.offer(nextWord);
}
}
}
}
transformations++;
}
return 0; // No transformation sequence found
}
public static void main(String[] args) {
WordLadderLength solution = new WordLadderLength();
// Example 1
String beginWord1 = "hit";
String endWord1 = "cog";
List<String> wordList1 = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
System.out.println(solution.ladderLength(beginWord1, endWord1, wordList1)); // Output: 5
// Example 2
String beginWord2 = "hit";
String endWord2 = "cog";
List<String> wordList2 = Arrays.asList("hot", "dot", "dog", "lot", "log");
System.out.println(solution.ladderLength(beginWord2, endWord2, wordList2)); // Output: 0
}
}
This Java code defines a WordLadderLength
class with the ladderLength
method, which uses BFS to find the length of the shortest transformation sequence. The provided test cases demonstrate its usage.
Python Solution
Here’s the equivalent Python solution for finding the length of the shortest transformation sequence from beginWord
to endWord
:
from collections import deque
class WordLadderLength:
def ladderLength(self, beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0 # If endWord is not in wordList, return 0
queue = deque()
visited = set()
queue.append(beginWord)
visited.add(beginWord)
transformations = 1
while queue:
size = len(queue)
for _ in range(size):
currentWord = queue.popleft()
# Generate all possible next words by changing one letter at a time
for j in range(len(currentWord)):
for c in range(ord('a'), ord('z') + 1):
nextWord = currentWord[:j] + chr(c) + currentWord[j + 1:]
if nextWord == endWord:
return transformations + 1 # Found the endWord
if nextWord in wordSet and nextWord not in visited:
visited.add(nextWord)
queue.append(nextWord)
transformations += 1
return 0 # No transformation sequence found
# Test cases
solution = WordLadderLength()
# Example 1
beginWord1 = "hit"
endWord1 = "cog"
wordList1 = ["hot", "dot", "dog", "lot", "log", "cog"]
print(solution.ladderLength(beginWord1, endWord1, wordList1)) # Output: 5
# Example 2
beginWord2 = "hit"
endWord2 = "cog"
wordList2 = ["hot", "dot", "dog", "lot", "log"]
print(solution.ladderLength(beginWord2, endWord2, wordList2)) # Output: 0
This Python code uses a similar structure as the Java solution. The WordLadderLength
class represents the solution, and the ladderLength
method performs BFS to find the length of the shortest transformation sequence. The provided test cases demonstrate its usage.