The link to the problem: https://leetcode.com/problems/word-ladder/
Given two words beginWord and endWord, and a dictionary wordList, return 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 word list.
Return 0 if there is no such transformation sequence.
Example
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.Thoughts:
This is a typical BFS problem. It is often to see people get confused with the two terms, BFS and DFS. It is actually not too hard to recognize them if we know their full name.
⚠️BFS stands for Breadth-First Search
⚠️DFS stands for Depth First Search.
For example, if we want to traverse a tree below.
- Depth First Search Traversal a tree: If see a node, we will continue traversing the next node that is adjacent to the next node until we can’t see any node or until we reach a visited node. Hence, if the starting node is 1 in the above tree, then the order of traversing nodes will be like: 1->2->4->5->3->7
- Breadth-First Search Traversal a tree: We can also say we traverse the nodes by level. Hence, the order of traversing nodes will be like: 1->2->3->4->5->7
The reason why we can say this is a BFS type question is that the concept “transforming one word to another” is similar to find the possible strings by level. (These possible strings might be our one of the path to our ending word.)
Before we introduce the code, let’s see several important variables:
- wordSet: the congregation of all the words in wordList that is given in the beginning. The reason why we use wordSet instead of using wordList is because of the low complexity of finding existing words.
wordSet contains all the possible words that we are allowed to transform. If a word was being used in our process of forming a new word, this word will be removed from wordSet. - levelSet: Storing all the strings that are waited to be transformed.
- nextLevelSet: Storing all the strings that we are going to traverse at the next level.
- level: counting the current number of transformations.
When we start to transform the word from beginWord, the level will be set as 1. Hence, if level = 2, means we are in the second transformation.
⚠️If we are at level x, we find a new word exactly the same as our ending word, we will return (x+1). Since we still need to do one more transform at the current level x, the ending word we found is actually at the next level. - curWord: the word that is going to be transformed. We will see whether we can convert the word into the ending word or any word in wordSet.
- newWord: a new word that is transformed from curWord. Once we form a new word which is also existed in the wordSet, we will add it to nextLevelSet.
We use the below graph to present all the words that have been placed into levelSet before.
The reason why the word "log" is not being placed into the set at level 4 is that we found that we can convert "dog" to "cog" before placing "log" into the set.
The below 169ms code beats 29% —
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord))
return 0;
int wordlen = beginWord.length();
Set<String> levelSet = new HashSet<>();
int level = 1;
levelSet.add(beginWord);
while(!levelSet.isEmpty())
{
Set<String> nextLevelSet = new HashSet<>();
for(String word: levelSet)
{
char[] curWord = word.toCharArray();
for(int i=0;i<wordlen;i++)
{
char originalC = curWord[i]; //change a letter
for(char c='a';c<='z';c++)
{
if(c==originalC)
continue;
curWord[i] = c;
String newWord = String.valueOf(curWord);
if(newWord.equals(endWord))
return level+1;
if(wordSet.contains(newWord))
{
nextLevelSet.add(newWord);
wordSet.remove(newWord);
}
}
curWord[i] = originalC; //redo
}
}
levelSet = nextLevelSet;
level++;
}
return 0;
}🚧There are two ways to improve the time complexity of the above code.
🔧1. We can remain the same logic, but this time, we use a queue instead of using levelSet and nextLevelSet which is initiated at every level
Below is the 85ms code that beats 41% —
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord))
return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int level = 1;
int wordlen = beginWord.length();
while(!queue.isEmpty())
{
int size = queue.size();
//get all words in this level
while(size>0)
{
char[] curWord = queue.poll().toCharArray();
//keep changing the chars in different position
for(int i=0;i<wordlen;i++)
{
char originalC = curWord[i];
for(char c='a';c<='z';c++)
{
if(c==originalC)
continue;
curWord[i] = c;
String newWord = String.valueOf(curWord);
if(newWord.equals(endWord))
return level+1;
if(wordSet.contains(newWord))
{
queue.offer(newWord);
wordSet.remove(newWord);
}
}
curWord[i] = originalC;
}
size--;
}
level++;
}
return 0;
}🔧2. The original idea is that we want to see how many levels are needed for us to convert the beginning word to the ending word. Now, we add another set called backwardSet, and we can use it to see how many levels are needed for us to convert the ending word to the beginning word.
However, we only use the backwardSet when the number of words in this set is more than our levelSet. We will just swap the two sets.
Hence, we will always let the number of words in levelSet more than the word numbers in backwardSet. In each level, we will just see if there’s any word in levelSet that can transform into the word in backwardSet.
Below is the 75ms code that beats 46% -
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord))
return 0;
int wordlen = beginWord.length();
Set<String> levelSet = new HashSet<>();
Set<String> backwardSet = new HashSet<>();
int level = 1;
levelSet.add(beginWord);
backwardSet.add(endWord);
while(!levelSet.isEmpty())
{
if(levelSet.size() < backwardSet.size())
{
//swap levelSet and backwardSet
Set<String> temp = levelSet;
levelSet = backwardSet;
backwardSet = temp;
}
Set<String> nextLevel = new HashSet<>();
wordSet.removeAll(levelSet);
for(String word: levelSet)
{
char[] curWord = word.toCharArray();
for(int i=0;i<wordlen;i++)
{
char originalC = curWord[i];
for(char c='a';c<='z';c++)
{
if(c==originalC)
continue;
curWord[i] = c;
String newWord = String.valueOf(curWord);
if(wordSet.contains(newWord))
{
if(backwardSet.contains(newWord))
return level+1;
nextLevel.add(newWord);
}
}
curWord[i] = originalC;
}
}
level++;
levelSet = nextLevel;
}
return 0;
}🔧2'. Based on the above idea, but using a helper method also boosts the code a little bit.
Below is the 55ms code that beats 65% —
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord))
return 0;
Set<String> levelSet = new HashSet<>();
levelSet.add(beginWord);
Set<String> backwardSet = new HashSet<>();
backwardSet.add(endWord);
return helper(levelSet,backwardSet,wordSet,1);
}
public int helper(Set<String> curSet,Set<String> targetSet, Set<String> wordSet,int level){
if(curSet.isEmpty() || targetSet.isEmpty())
return 0;
Set<String> nextSet = new HashSet<>();
for(String word: curSet)
{
char[] curWord = word.toCharArray();
for(int i=0;i<word.length();i++)
{
char originalC = curWord[i];
for(char c='a';c<='z';c++)
{
if(c==originalC)
continue;
curWord[i] = c;
String newWord = String.valueOf(curWord);
if(wordSet.contains(newWord))
{
if(targetSet.contains(newWord))
return level+1;
nextSet.add(newWord);
}
}
curWord[i] = originalC;
}
}
wordSet.removeAll(nextSet);
if(nextSet.size()<targetSet.size())
return helper(targetSet,nextSet,wordSet,level+1);
else
return helper(nextSet,targetSet,wordSet,level+1);
}
