Problem: Word Ladder
Problem Statement:
Given two words, beginWord and endWord, and a dictionary wordList, find the length of the shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the dictionary.
Note:
- You must implement a function that returns the length of the shortest transformation sequence.
- If there is no such transformation sequence, return 0.
Example 1:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output:
5
Explanation: The 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: There is no possible transformation sequence from hit to cog because the word cog is not in the word list.
Approach:
The problem can be thought of as finding the shortest path in an unweighted graph, where:
- Each word in the word list is a node.
- An edge exists between two nodes (words) if they differ by exactly one character.
Steps:
- BFS (Breadth-First Search) is the optimal approach for finding the shortest path in an unweighted graph. We explore all possible transformations from the
beginWordto find the shortest path toendWord. - Each word in the BFS queue is associated with the number of steps taken to reach that word.
- As soon as we reach the
endWord, we return the number of steps (which represents the length of the transformation sequence). - If we exhaust the queue without finding
endWord, return 0.
Time Complexity:
- Time Complexity: O(N×M)O(N \times M)O(N×M), where
Nis the number of words in the word list andMis the length of each word. This is because for each word, we generate all possible intermediate words by replacing each character one by one. - Space Complexity: O(N)O(N)O(N), since we store the word list and BFS queue.
Algorithm:
- Start BFS from the
beginWord. - For each word, generate all possible words by changing each character to
*and check if it’s in the dictionary (word list). - Track the level (or depth) of BFS.
- If we reach the
endWord, return the number of steps taken. - If no transformation is possible, return 0.
Code Implementations
1. Python Code
from collections import deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
wordList.add(beginWord)
queue = deque([(beginWord, 1)]) # (current_word, current_length)
visited = set([beginWord])
while queue:
word, length = queue.popleft()
# Try changing each character of the word
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == endWord:
return length + 1
if new_word in wordList and new_word not in visited:
visited.add(new_word)
queue.append((new_word, length + 1))
return 0
# Example test cases
beginWord = "hit"
endWord = "cog"
wordList = set(["hot", "dot", "dog", "lot", "log", "cog"])
print(ladderLength(beginWord, endWord, wordList)) # Output: 5
2. C++ Code
#include <iostream>
#include <unordered_set>
#include <queue>
#include <string>
using namespace std;
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
if (wordList.find(endWord) == wordList.end()) return 0;
wordList.insert(beginWord);
queue<pair<string, int>> q; // {current_word, length}
unordered_set<string> visited;
q.push({beginWord, 1});
visited.insert(beginWord);
while (!q.empty()) {
auto [word, length] = q.front();
q.pop();
// Try changing each character of the word
for (int i = 0; i < word.length(); i++) {
char original = word[i];
for (char c = 'a'; c <= 'z'; c++) {
word[i] = c;
if (word == endWord) return length + 1;
if (wordList.find(word) != wordList.end() && visited.find(word) == visited.end()) {
visited.insert(word);
q.push({word, length + 1});
}
}
word[i] = original; // Restore original character
}
}
return 0;
}
int main() {
string beginWord = "hit";
string endWord = "cog";
unordered_set<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
cout << ladderLength(beginWord, endWord, wordList) << endl; // Output: 5
return 0;
}
3. Java Code
import java.util.*;
public class WordLadder {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if (!wordList.contains(endWord)) return 0;
wordList.add(beginWord);
Queue<Pair<String, Integer>> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new Pair<>(beginWord, 1));
visited.add(beginWord);
while (!queue.isEmpty()) {
Pair<String, Integer> current = queue.poll();
String word = current.getKey();
int length = current.getValue();
for (int i = 0; i < word.length(); i++) {
char[] temp = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
temp[i] = c;
String newWord = new String(temp);
if (newWord.equals(endWord)) return length + 1;
if (wordList.contains(newWord) && !visited.contains(newWord)) {
visited.add(newWord);
queue.offer(new Pair<>(newWord, length + 1));
}
}
}
}
return 0;
}
public static void main(String[] args) {
WordLadder wl = new WordLadder();
Set<String> wordList = new HashSet<>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
System.out.println(wl.ladderLength("hit", "cog", wordList)); // Output: 5
}
}
class Pair<K, V> {
K key;
V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() { return key; }
public V getValue() { return value; }
}
4. C# Code
using System;
using System.Collections.Generic;
public class WordLadder {
public int LadderLength(string beginWord, string endWord, HashSet<string> wordList) {
if (!wordList.Contains(endWord)) return 0;
wordList.Add(beginWord);
Queue<KeyValuePair<string, int>> queue = new Queue<KeyValuePair<string, int>>();
HashSet<string> visited = new HashSet<string>();
queue.Enqueue(new KeyValuePair<string, int>(beginWord, 1));
visited.Add(beginWord);
while (queue.Count > 0) {
var current = queue.Dequeue();
string word = current.Key;
int length = current.Value;
for (int i = 0; i < word.Length; i++) {
char[] temp = word.ToCharArray();
for (char c = 'a'; c <= 'z'; c++) {
temp[i] = c;
string newWord = new string(temp);
if (newWord == endWord) return length + 1;
if (wordList.Contains(newWord) && !visited.Contains(newWord)) {
visited.Add(newWord);
queue.Enqueue(new KeyValuePair<string, int>(newWord, length + 1));
}
}
}
}
return 0;
}
public static void Main() {
WordLadder wl = new WordLadder();
HashSet<string> wordList = new HashSet<string> { "hot", "dot", "dog", "lot", "log", "cog" };
Console.WriteLine(wl.LadderLength("hit", "cog", wordList)); // Output: 5
}
}
5. JavaScript Code
function ladderLength(beginWord, endWord, wordList) {
if (!wordList.has(endWord)) return 0;
wordList.add(beginWord);
let queue = [[beginWord, 1]]; // [current_word, current_length]
let visited = new Set([beginWord]);
while (queue.length > 0) {
let [word, length] = queue.shift();
for (let i = 0; i < word.length; i++) {
for (let c = 'a'; c <= 'z'; c++) {
let newWord = word.slice(0, i) + c + word.slice(i + 1);
if (newWord === endWord) return length + 1;
if (wordList.has(newWord) && !visited.has(newWord)) {
visited.add(newWord);
queue.push([newWord, length + 1]);
}
}
}
}
return 0;
}
// Example test cases
let beginWord = "hit";
let endWord = "cog";
let wordList = new Set(["hot", "dot", "dog", "lot", "log", "cog"]);
console.log(ladderLength(beginWord, endWord, wordList)); // Output: 5
Summary of Code Logic:
- BFS: We use BFS to explore all possible transformations, layer by layer, until we find the shortest transformation sequence.
- Word Generation: For each word, we generate all possible words by changing one character at a time, checking if they are valid transformations (i.e., present in the dictionary).
- Visited Set: We maintain a visited set to avoid revisiting words and getting stuck in infinite loops.
- Queue: We store each word in the queue with its current transformation length.
Time Complexity:
- Time Complexity: O(N×M)O(N \times M)O(N×M), where
Nis the number of words andMis the length of each word. - Space Complexity: O(N)O(N)O(N), for storing words in the visited set and the queue.