Word Ladder - LeetCode
Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/word-ladder.
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, and wordList[i] consist of lowercase English letters
- beginWord != endWord
- All the words in wordList are unique.
Solutions for World Ladder
Approach 1
The idea is to use BFS traversal. Two adjacent words can be considered as nodes of the graph. The count of the number of different characters between the two words can be considered as the distance. If the difference is 1, we return the count. Else we consider every other word in the wordList and check the difference. If the difference is 1, we push the word to the queue.
The algorithmic flow of this approach is as follows:
- i = 1
q = new Queue()
q.push(beginWord)
set count = 1
- initialize set<string> s
s.insert(begin)
- loop while !q.empty()
- size = q.size()
- for i = 0; i < size; i++
- currentWord = q.first()
- q.pop()
- if currentWord == endWord
- return count
- end if
// check stores the count of the number of characters different
// in the currentWord and endWord
- check = 0
- for i = 0; i < currentWord.length; i++
- if currentWord[i] != endWord[i]
- count++
- end if
- end for
// if the number of different characters is 1, this means
// we have reached the endWord and return count
- if check == 1
- return count
- end if
// add the next word to the queue
- loop for j = 0; j < wordList.size(); j++
- set diff = 0
- loop for k = 0; k < currentWord.size(); k++
- if currentWord[k] != wordList[j][k]
- increment diff++
- end if
- end for
- if diff == 1
- if
- end if
- end for
- end for
- end while
// if we cannot reach the endWord, we return -1
- return -1
The time complexity of this approach is O(n * n * m). Where m is the length of each string. The space complexity is O(n), as we are using an additional space in terms of the queue.
Approach 2
Another approach is to use BFS traversal along with Trie data structure.
The algorithmic flow of this approach is as follows:
- set TrieNode *root = new TrieNode
- q = new Queue()
q.push(beginWord)
// create a hash map of visited node
unordered_map<string, int> map;
- for i = 0; i < wordList.size; i++
- map[wordList[i]] = 0
- end for
map[beginWord] = 1
- loop while !q.empty()
- currentWord = q.first()
- q.pop()
- if currentWord == endWord
- return map[str]
- end if
// initialize allPossible vector
- vector<string> allPossible
- allPermutations(root, currentWord, allPossible)
- loop for string x: allPossible
- if map.count(x) == 0
- q.push(x)
- map[x] = map[str] + 1
- end if
- end for
- end while
-
// allPermutations(root, currentWord, allPossible, currentString = '', changed = false, i = 0)
- if root == NULL
- return
- end if
- if currentWord.size() == currentString.size()
- if root -> endOfWord
- allPossible.push_back(currentString)
- return
- end if
- end if
- loop for auto x: root -> children
- currentString.push_back(x.first)
- if x.first == currentWord[i]
- allPermutations(x.second, currentWord, allPossible, currentString, changed, i + 1)
- else if !changed
- allPermutations(x.second, currentWord, allPossible, currentString, !changed, i + 1)
- end if
// BackTrack.
currentString.pop_back();
- end for
Both the time and space complexity of this approach is O(n * m * m). Where m is the length of each string.
Approach 3
Another approach to solving this problem via the BFS approach is using a Queue and Set. To find the shortest path, we start from the beginWord and push it into a queue. If the endWord is found, then we return that level of BFS. If we fail to find the endWord in the first iteration, we generate all the words by replacing each character in the string with a till z. When the endWord is found, we return the length of the shortest chain of words.
Algorithm
The algorithmic flow of this approach is as follows:
- create set set<string> s(wordList.begin(), wordList.end())
// If the target endWord is not
// present in the set return 0
- if s.find(endWord) == s.end()
- return 0
- end if
// initialize queue and push the startWord
- queue<string> q
q.push(beginWord)
- set result = 0
initialize i, j, size
char k
string currentWord
int wordLength = beginWord.size()
- loop while !q.empty
- ++result
- size = q.size()
// update the queue while traversing with words
// that are present in the set
- loop for i = 0; i < size; i++
- currentWord = q.front()
- q.pop()
// loop to traverse every character of the word
- loop for j = 0; j < wordLength; j++
- set char originalChar = currentWord[j]
// replace the current character in the word
// with every possible alphabhet
- loop for k = 'a'; k <= 'z'; k++
- set currentWord[j] = k
// if we find the endWord, return result + 1
- if currentWord == endWord
- return result + 1
- end if
// if the currentWord is not in the set, continue
// the loop else remove it from the set
- if s.find(currentWord) == s.end()
- continue
- end if
// push the newly generated word to the queue
q.push(currentWord)
- end for
- currentWord[j] = originalChar
- end for
- end for
- end while
- return 0
The time complexity of the above approach is O(n), and the space complexity is O(1).
Check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
set<string> s(wordList.begin(), wordList.end());
// If the target endWord is not
// present in the set return 0
if(s.find(endWord) == s.end()) {
return 0;
}
queue<string> q;
// push the beginWord to queue
q.push(beginWord);
int result = 0;
int i, j, size;
char k;
string currentWord;
int wordLength = beginWord.size();
// While the queue is non-empty
while(!q.empty()) {
++result;
size = q.size();
// update the queue while traversing with words
// that are present in the set
for(i = 0; i < size; i++) {
currentWord = q.front();
q.pop();
// loop to traverse every character of the word
for(j = 0; j < wordLength; j++) {
char originalChar = currentWord[j];
// replace the current character in the word
// with every possible alphabhet
for(k = 'a'; k <= 'z'; k++) {
currentWord[j] = k;
// if we find the endWord, return result + 1
if(currentWord == endWord) {
return result + 1;
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if(s.find(currentWord) == s.end()) {
continue;
}
s.erase(currentWord);
// push the newly generated word to the queue
q.push(currentWord);
}
currentWord[j] = originalChar;
}
}
}
return 0;
}
};Golang solution
func ladderLength(beginWord string, endWord string, wordList []string) int {
s := make(map[string]bool)
for _, word := range wordList {
s[word] = true
}
// If the target endWord is not
// present in the set return 0
if _, ok := s[endWord]; !ok {
return 0
}
q := []string{}
// push the beginWord to queue
q = append(q, beginWord)
result := 0
wordLength := len(beginWord)
// While the queue is non-empty
for len(q) > 0 {
result += 1
size := len(q)
// update the queue while traversing with words
// that are present in the set
for i := 0; i < size; i++ {
currentWord := q[0]
q = q[1:]
// loop to traverse every character of the word
for j := 0; j < wordLength; j++ {
originalChar := currentWord[j]
// replace the current character in the word
// with every possible alphabhet
for k := 'a'; k <= 'z'; k++ {
currentWord = replaceAtIndex(currentWord, k, j)
// if we find the endWord, return result + 1
if currentWord == endWord {
return result + 1
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if _, ok := s[currentWord]; !ok {
continue
}
delete(s, currentWord)
// push the newly generated word to the queue
q = append(q, currentWord)
}
currentWord = replaceAtIndex(currentWord, rune(originalChar), j)
}
}
}
return 0
}
func replaceAtIndex(in string, r rune, i int) string {
out := []rune(in)
out[i] = r
return string(out)
}JavaScript solution
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
var s = new Set(wordList);
// If the target endWord is not
// present in the set return 0
if(!s.has(endWord)) {
return 0;
}
// variable q will act as queue
var q = [];
// push the beginWord to queue
q.push(beginWord);
let result = 0;
let i, j, size;
let k;
let currentWord;
let wordLength = beginWord.length;
// While the queue is non-empty
while(q.length !== 0) {
++result;
size = q.length;
// update the queue while traversing with words
// that are present in the set
for(i = 0; i < size; i++) {
currentWord = q.shift();
// loop to traverse every character of the word
for(j = 0; j < wordLength; j++) {
let originalChar = currentWord[j];
// replace the current character in the word
// with every possible alphabhet
for(k = 97; k <= 122; k++) {
currentWord = currentWord.substring(0, j) + String.fromCharCode(k) + currentWord.substring(j + 1);
// if we find the endWord, return result + 1
if(currentWord === endWord) {
return result + 1;
}
// if the currentWord is not in the set, continue
// the loop else remove it from the set
if(!s.has(currentWord)) {
continue;
}
s.delete(currentWord);
// push the newly generated word to the queue
q.push(currentWord);
}
currentWord = currentWord.substring(0, j) + originalChar + currentWord.substring(j + 1);
}
}
}
return 0;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Step 1: set<string> s(wordList.begin(), wordList.end())
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Step 2: if s.find(endWord) == s.end()
s.find('cog') == s.end()
false
Step 3: queue<string> q
q = []
q.push(startWord)
q = ['hit']
int result = 0
int i, j, size
char k
string currentWord
wordLength = beginWord.size()
= 'hit'.size()
= 3
Step 4: loop while !q.empty()
q = ['hit']
q.empty() = false
!q.empty()
true
++result
result = 1
size = q.size()
= 1
loop for i = 0; i < size;
i < size
0 < 1
true
currentWord = q.front()
= 'hit'
q.pop()
q = []
loop for j = 0; j < wordLength
j < wordLength
0 < 3
true
originalChar = currentWord[j]
= 'hit'[0]
= 'h'
loop for k = 'a'; k <= 'z';
a <= 'z'
true
currentWord[j] = k
currentWord[0] = 'a'
currentWord = 'ait'
if currentWord == endWord
'ait' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('ait') == s.end()
// as the set s does not include 'ait' so the condition is true
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
true
continue
k++
k = 'b'
the loop continues till 'z' as we don't have any word
'bit', 'cit',...'hit'...'zit' in the list.
currentWord[j] = originalChar
currentWord[0] = 'h'
currentWord = 'hit'
j++
j = 1
loop for j < wordLength
j < wordLength
1 < 3
true
originalChar = currentWord[j]
= 'hit'[1]
= 'i'
loop for k = 'a'; k <= 'z';
a <= 'z'
true
currentWord[j] = k
currentWord[1] = 'a'
currentWord = 'hat'
if currentWord == endWord
'hat' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('hat') == s.end()
// as the set s does not include 'hat' so the condition is true
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
true
continue
k++
k = 'b'
the loop continues till 'n' as we don't have any word
'hbt', 'hct', 'hdt'..'hnt' in the list.
when k = 'o'
we get 'hot'
currentWord[j] = k
currentWord[1] = 'o'
currentWord = 'hot'
if currentWord == endWord
'hot' == 'cog'
false
if s.find(currentWord) == s.end()
s.find('hot') == s.end()
// as the set s does include 'hot' so the condition is false
s = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
false
s.erase(currentWord)
s.erase('hot')
s = ['dot', 'dog', 'lot', 'log', 'cog']
q.push(currentWord)
q.push('hot')
q = ['hot']
The loop continues till k is equal to `z` and the loop repeats.
The sequence we follow goes like
'hit' -> 'hot' -> 'dot' -> 'dog' -> 'cog'
We return the result as 5.