Word Ladder
Word Ladder – Hard Level Problem
You are given two words, beginWord and endWord, along with a list of words called wordList. All words are of equal length, made up of lowercase English letters, and are unique.
The task is to transform beginWord into endWord following these rules:
- You can change beginWord to any word in wordList if they differ by exactly one character in one position, while all other characters match.
- Repeat this transformation with the newly obtained word as many times as needed.
Return the minimum number of transformations required to turn beginWord into endWord, or 0 if no valid sequence exists.
Examples related to Word Ladder Problem
Example 1:
Input:
beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]
Output: 4
Explanation: Transformation sequence is "cat" -> "bat" -> "bag" -> "sag".
Output: 4
Explanation: Transformation sequence is "cat" -> "bat" -> "bag" -> "sag".
Example 2:
Input:
beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]
Output: 0
Explanation: No possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.
Output: 0
Explanation: No possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.
Constraints:
- 1 <= beginWord.length <= 10
- 1 <= wordList.length <= 100
Hints to solve Word Ladder Problem
Recommended Time & Space Complexity
Aim for a solution with O((m²) * n) time and O((m²) * n) space, where n is the number of words in the list and m is the length of each word.
Hint 1:
Visualize the problem as a graph where words are nodes, and an edge exists between two words if they differ by one character.
A simple method is to compare all word pairs, but can you optimize this?
For instance, consider how words like “hot” can connect to other words by changing one letter.
Hint 2:
To build connections efficiently, create “intermediate states” by replacing one letter of a word with *.
For example, “hot” can be transformed into patterns like *ot, h*t, and ho*. These patterns act as bridges connecting words that differ by one character.
Store each word as a neighbor to its patterns and use BFS to traverse from beginWord, keeping track of visited words with a hash set.
Hint 3:
During BFS, if you visit a word that matches endWord, return the length of the transformation sequence.
For each word, generate its pattern states and explore connected words that haven’t been visited yet.
If the queue is exhausted without reaching endWord, return 0.
Methods to Solve Word Ladder Problem
There are mainly 4 approaches to Solve Word Ladder Problem:
- Breadth First Search – I
- Breadth First Search – II
- Breadth First Search – III
- Meet In The Middle (BFS)
1. Breadth First Search – I Method
Use BFS to explore all possible one-character transformations level by level, starting from beginWord. The shortest path to endWord gives the minimum transformation sequence.
- Time complexity: O(n^2∗m)
- Space complexity: O(n^2)
Where n is the number of words and m is the length of the word.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end() ||
beginWord == endWord) {
return 0;
}
int n = wordList.size();
int m = wordList[0].size();
vector<vector<int>> adj(n);
unordered_map<string, int> mp;
for (int i = 0; i < n; i++) {
mp[wordList[i]] = i;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cnt = 0;
for (int k = 0; k < m; k++) {
if (wordList[i][k] != wordList[j][k]) {
cnt++;
}
}
if (cnt == 1) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
queue q;
int res = 1;
unordered_set visit;
for (int i = 0; i < m; i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == beginWord[i]) {
continue;
}
string word = beginWord.substr(0, i) + c + beginWord.substr(i + 1);
if (mp.find(word) != mp.end() && visit.find(mp[word]) == visit.end()) {
q.push(mp[word]);
visit.insert(mp[word]);
}
}
}
while (!q.empty()) {
res++;
int size = q.size();
for (int i = 0; i < size; i++) {
int node = q.front();
q.pop();
if (wordList[node] == endWord) {
return res;
}
for (int nei : adj[node]) {
if (visit.find(nei) == visit.end()) {
visit.insert(nei);
q.push(nei);
}
}
}
}
return 0;
}
};
Java
public class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
if (!wordList.contains(endWord) || beginWord.equals(endWord)) {
return 0;
}
int n = wordList.size();
int m = wordList.get(0).length();
List<List> adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
Map<String, Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++) {
mp.put(wordList.get(i), i);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cnt = 0;
for (int k = 0; k < m; k++) {
if (wordList.get(i).charAt(k) != wordList.get(j).charAt(k)) {
cnt++;
}
}
if (cnt == 1) {
adj.get(i).add(j);
adj.get(j).add(i);
}
}
}
Queue<Integer> q = new LinkedList<>();
int res = 1;
Set<Integer> visit = new HashSet<>();
for (int i = 0; i < m; i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == beginWord.charAt(i)) {
continue;
}
String word = beginWord.substring(0, i) + c + beginWord.substring(i + 1);
if (mp.containsKey(word) && !visit.contains(mp.get(word))) {
q.add(mp.get(word));
visit.add(mp.get(word));
}
}
}
while (!q.isEmpty()) {
res++;
int size = q.size();
for (int i = 0; i < size; i++) {
int node = q.poll();
if (wordList.get(node).equals(endWord)) {
return res;
}
for (int nei : adj.get(node)) {
if (!visit.contains(nei)) {
visit.add(nei);
q.add(nei);
}
}
}
}
return 0;
}
}
Python
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if (endWord not in wordList) or (beginWord == endWord):
return 0
n, m = len(wordList), len(wordList[0])
adj = [[] for _ in range(n)]
mp = {}
for i in range(n):
mp[wordList[i]] = i
for i in range(n):
for j in range(i + 1, n):
cnt = 0
for k in range(m):
if wordList[i][k] != wordList[j][k]:
cnt += 1
if cnt == 1:
adj[i].append(j)
adj[j].append(i)
q, res = deque(), 1
visit = set()
for i in range(m):
for c in range(97, 123):
if chr(c) == beginWord[i]:
continue
word = beginWord[:i] + chr(c) + beginWord[i + 1:]
if word in mp and mp[word] not in visit:
q.append(mp[word])
visit.add(mp[word])
while q:
res += 1
for i in range(len(q)):
node = q.popleft()
if wordList[node] == endWord:
return res
for nei in adj[node]:
if nei not in visit:
visit.add(nei)
q.append(nei)
return 0
JavaScript
class Solution {
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
ladderLength(beginWord, endWord, wordList) {
if (!wordList.includes(endWord) ||
beginWord === endWord) {
return 0;
}
const n = wordList.length;
const m = wordList[0].length;
const adj = Array.from({ length: n }, () => []);
const mp = new Map();
for (let i = 0; i < n; i++) {
mp.set(wordList[i], i);
}
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let cnt = 0;
for (let k = 0; k < m; k++) {
if (wordList[i][k] !== wordList[j][k]) {
cnt++;
}
}
if (cnt === 1) {
adj[i].push(j);
adj[j].push(i);
}
}
}
const q = new Queue();
let res = 1;
const visit = new Set();
for (let i = 0; i < m; i++) {
for (let c = 97; c < 123; c++) {
if (String.fromCharCode(c) === beginWord[i]) {
continue;
}
const word = beginWord.slice(0, i) +
String.fromCharCode(c) + beginWord.slice(i + 1);
if (mp.has(word) && !visit.has(mp.get(word))) {
q.push(mp.get(word));
visit.add(mp.get(word));
}
}
}
while (!q.isEmpty()) {
res++;
let size = q.size();
for (let i = 0; i < size; i++) {
let node = q.pop();
if (wordList[node] === endWord) {
return res;
}
for (let nei of adj[node]) {
if (!visit.has(nei)) {
visit.add(nei);
q.push(nei);
}
}
}
}
return 0;
}
}
2. Breadth First Search – II
This BFS variant optimizes by generating intermediate patterns (e.g., *ot for “hot”) to find valid transformations faster. It avoids direct word-to-word comparisons.
- Time complexity: O(m^2∗n)
- Space complexity: O(m^2∗n)
Where n is the number of words and m is the length of the word.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
nordered_set<string>
words(wordList.begin(), wordList.end());
if (words.find(endWord) == words.end() || beginWord == endWord) return 0;
int res = 0;
queue<string> q;
q.push(beginWord);
while (!q.empty()) {
res++;
int len = q.size();
for (int i = 0; i < len; i++) {
string node = q.front();
q.pop();
if (node == endWord) return res;
for (int j = 0; j < node.length(); j++) {
char original = node[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
node[j] = c;
if (words.find(node) != words.end()) {
q.push(node);
words.erase(node);
}
}
node[j] = original;
}
}
}
return 0;
}
};
Java
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord) || beginWord.equals(endWord)) return 0;
Set<String>words = new HashSet<>(wordList);
int res = 0;
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
while (!q.isEmpty()) {
res++;
for (int i = q.size(); i > 0; i--) {
String node = q.poll();
if (node.equals(endWord)) return res;
for (int j = 0; j < node.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == node.charAt(j)) continue;
String nei = node.substring(0, j) + c + node.substring(j + 1);
if (words.contains(nei)) {
q.offer(nei);
words.remove(nei);
}
}
}
}
}
return 0;
}
}
Python
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if (endWord not in wordList) or (beginWord == endWord):
return 0
words, res = set(wordList), 0
q = deque([beginWord])
while q:
res += 1
for _ in range(len(q)):
node = q.popleft()
if node == endWord:
return res
for i in range(len(node)):
for c in range(97, 123):
if chr(c) == node[i]:
continue
nei = node[:i] + chr(c) + node[i + 1:]
if nei in words:
q.append(nei)
words.remove(nei)
return 0
JavaScript
class Solution {
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
ladderLength(beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord) || beginWord === endWord) {
return 0;
}
let res = 0;
const q = new Queue([beginWord]);
while (!q.isEmpty()) {
res++;
let len = q.size();
for (let i = 0; i < len; i++) {
const node = q.pop();
if (node === endWord) return res;
for (let j = 0; j < node.length; j++) {
for (let c = 97; c < 123; c++) {
if (String.fromCharCode(c) === node[j]) {
continue;
}
const nei = node.slice(0, j) +
String.fromCharCode(c) +
node.slice(j + 1);
if (words.has(nei)) {
q.push(nei);
words.delete(nei);
}
}
}
}
}
return 0;
}
}
3. Breadth First Search – III
Enhance BFS by precomputing and storing neighbors for each word. This reduces repetitive computations during traversal, speeding up the process for large word lists.
- Time complexity: O(m^2∗n)
- Space complexity: O(m^2∗n)
Where n is the number of words and m is the length of the word.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (endWord.empty() || find(wordList.begin(), wordList.end(), endWord) == wordList.end()) {
return 0;
}
unordered_map<string, vector<string>> nei;
wordList.push_back(beginWord);
for (const string& word : wordList) {
for (int j = 0; j < word.size(); ++j) {
string pattern = word.substr(0, j) + "*" + word.substr(j + 1);
nei[pattern].push_back(word);
}
}
unordered_set<string> visit{beginWord};
queue<string> q;
q.push(beginWord);
int res = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
string word = q.front();
q.pop();
if (word == endWord) {
return res;
}
for (int j = 0; j < word.size(); ++j) {
string pattern = word.substr(0, j) + "*" + word.substr(j + 1);
for (const string& neiWord : nei[pattern]) {
if (visit.find(neiWord) == visit.end()) {
visit.insert(neiWord);
q.push(neiWord);
}
}
}
}
++res;
}
return 0;
}
};
Java
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
Map<String, List<String>> nei = new HashMap<>();
wordList.add(beginWord);
for (String word : wordList) {
for (int j = 0; j < word.length(); j++) { String pattern = word.substring(0, j) + "*" + word.substring(j + 1); nei.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
}
}
Set<String> visit = new HashSet<>();
Queue<String> q= new LinkedList<>();
q.offer(beginWord);
int res = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String word = q.poll();
if (word.equals(endWord)) {
return res;
}
for (int j = 0; j < word.length(); j++) {
String pattern = word.substring(0, j) + "*" + word.substring(j + 1);
for (String neiWord : nei.getOrDefault(pattern, Collections.emptyList())) {
if (!visit.contains(neiWord)) {
visit.add(neiWord);
q.offer(neiWord);
}
}
}
}
res++;
}
return 0;
}
}
Python
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
nei = collections.defaultdict(list)
wordList.append(beginWord)
for word in wordList:
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1 :]
nei[pattern].append(word)
visit = set([beginWord])
q = deque([beginWord])
res = 1
while q:
for i in range(len(q)):
word = q.popleft()
if word == endWord:
return res
for j in range(len(word)):
pattern = word[:j] + "*" + word[j + 1 :]
for neiWord in nei[pattern]:
if neiWord not in visit:
visit.add(neiWord)
q.append(neiWord)
res += 1
return 0
JavaScript
class Solution {
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
ladderLength(beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) {
return 0;
}
const nei = {};
wordList.push(beginWord);
for (const word of wordList) {
for (let j = 0; j < word.length; ++j) {
const pattern = word.substring(0, j) +
'*' + word.substring(j + 1);
if (!nei[pattern]) {
nei[pattern] = [];
}
nei[pattern].push(word);
}
}
const visit = new Set([beginWord]);
const q =new Queue([beginWord]);
let res = 1;
while (!q.isEmpty()) {
const size = q.size();
for (let i = 0; i < size; ++i) {
const word = q.pop();
if (word === endWord) {
return res;
}
for (let j = 0; j < word.length; ++j) {
const pattern = word.substring(0, j) +
'*' + word.substring(j + 1);
for (const neiWord of nei[pattern]) {
if (!visit.has(neiWord)) {
visit.add(neiWord);
q.push(neiWord);
}
}
}
}
++res;
}
return 0;
}
}
4. Meet In The Middle (BFS)
Perform two simultaneous BFS traversals, one from beginWord and the other from endWord. The search meets in the middle, significantly reducing the number of explored nodes.
- Time complexity: O(m^2∗n)
- Space complexity: O(m^2∗n)
Where n is the number of words and m is the length of the word.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end() ||
beginWord == endWord)
return 0;
int m = wordList[0].size();
unordered_set<string>
wordSet(wordList.begin(), wordList.end());
queue<string>qb, qe;
unordered_map<string, int> fromBegin, fromEnd;
qb.push(beginWord);
qe.push(endWord);
fromBegin[beginWord] = 1;
fromEnd[endWord] = 1;
while (!qb.empty() && !qe.empty()) {
if (qb.size() > qe.size()) {
swap(qb, qe);
swap(fromBegin, fromEnd);
}
int size = qb.size();
for (int k = 0; k < size; k++) {
string word = qb.front();
qb.pop();
int steps = fromBegin[word];
for (int i = 0; i < m; i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word[i])
continue;
string nei = word.substr(0, i) +
c + word.substr(i + 1);
if (!wordSet.count(nei))
continue;
if (fromEnd.count(nei))
return steps + fromEnd[nei];
if (!fromBegin.count(nei)) {
fromBegin[nei] = steps + 1;
qb.push(nei);
}
}
}
}
}
return 0;
}
};
Java
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord) || beginWord.equals(endWord))
return 0;
int m = wordList.get(0).length();
Set<String> wordSet = new HashSet<>(wordList);
Queue<String> qb = new LinkedList<>(), qe = new LinkedList<>();
Map<String, Integer> fromBegin = new HashMap<>();
Map<String, Integer> fromEnd = new HashMap<>();
qb.add(beginWord);
qe.add(endWord);
fromBegin.put(beginWord, 1);
fromEnd.put(endWord, 1);
while (!qb.isEmpty() && !qe.isEmpty()) {
if (qb.size() > qe.size()) {
Queue<String>tempQ = qb;
qb = qe;
qe = tempQ;
Map<String, Integer> tempMap = fromBegin;
fromBegin = fromEnd;
fromEnd = tempMap;
}
int size = qb.size();
for (int k = 0; k < size; k++) {
String word = qb.poll();
int steps = fromBegin.get(word);
for (int i = 0; i < m; i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(i))
continue;
String nei = word.substring(0, i) +
c + word.substring(i + 1);
if (!wordSet.contains(nei))
continue;
if (fromEnd.containsKey(nei))
return steps + fromEnd.get(nei);
if (!fromBegin.containsKey(nei)) {
fromBegin.put(nei, steps + 1);
qb.add(nei);
}
}
}
}
}
return 0;
}
}
Python
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or beginWord == endWord:
return 0
m = len(wordList[0])
wordSet = set(wordList)
qb, qe = deque([beginWord]), deque([endWord])
fromBegin, fromEnd = {beginWord: 1}, {endWord: 1}
while qb and qe:
if len(qb) > len(qe):
qb, qe = qe, qb
fromBegin, fromEnd = fromEnd, fromBegin
for _ in range(len(qb)):
word = qb.popleft()
steps = fromBegin[word]
for i in range(m):
for c in range(97, 123):
if chr(c) == word[i]:
continue
nei = word[:i] + chr(c) + word[i + 1:]
if nei not in wordSet:
continue
if nei in fromEnd:
return steps + fromEnd[nei]
if nei not in fromBegin:
fromBegin[nei] = steps + 1
qb.append(nei)
return 0
JavaScript
class Solution {
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
ladderLength(beginWord, endWord, wordList) {
if (!wordList.includes(endWord) ||
beginWord === endWord) {
return 0;
}
const m = wordList[0].length;
const wordSet = new Set(wordList);
let qb = new Queue([beginWord]);
let qe = new Queue([endWord]);
let fromBegin = { [beginWord]: 1 };
let fromEnd = { [endWord]: 1 };
while (!qb.isEmpty() && !qe.isEmpty()) {
if (qb.size() > qe.size()) {
[qb, qe] = [qe, qb];
[fromBegin, fromEnd] = [fromEnd, fromBegin];
}
const size = qb.size();
for (let k = 0; k < size; k++) {
const word = qb.pop();
const steps = fromBegin[word];
for (let i = 0; i < m; i++) {
for (let c = 97; c <= 122; c++) {
if (String.fromCharCode(c) === word[i])
continue;
const nei = word.slice(0, i) +
String.fromCharCode(c) +
word.slice(i + 1);
if (!wordSet.has(nei))
continue;
if (fromEnd[nei] !== undefined)
return steps + fromEnd[nei];
if (fromBegin[nei] === undefined) {
fromBegin[nei] = steps + 1;
qb.push(nei);
}
}
}
}
}
return 0;
}
}
