問題連結: https://leetcode.com/problems/word-ladder/
給予兩個字串 beginWord 和endWord, 以及一個list稱 wordList,
求回傳我們從beginWord 變形到endWord所需花的最短變形次數, 而變形的過程都需要從wordList裡面拿, 且一次只能變一個字母
若無法轉換成功 則回傳0
範例
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.想法:
這題是典型的BFS題目, BFS全名是Breadth First Search, 常常看到有人會把BFS跟DFS(Depth First Search)搞混, 其實只要知道他們的全名就大概可以知道他們是什麼意思
比如當我們想要走訪整個樹如下圖
若用DFS的方式, 我們是碰到一個節點後就會繼續一直往下走直到我們走道盡頭或者遇到已訪過的節點, 就會往回走找下一個有連接點的節點, 所以走訪節點, 假設起點是1的話, 順序將會是像這樣: 1->2->4->5->3->7
若用BFS的方式, 變成我們有點像是走訪這些節點 level-by-level, 我們訪過第一層的節點後, 我們才會訪下一層的節點, 所以就是走訪節點順序將會是像這樣: 1->2->3->4->5->7
而為何我們可以認定這題可以用BFS來解是因為這題要求我們做的"變形", 很像是要我們找每個level的字串(找變形的路程)直到我們找到我們最終要的指定字串
在介紹程式碼前, 先來介紹幾個重要變數:
- wordSet: 其實就是一開始給予的wordList裡面所有字串的集合, 會用wordSet而不是直接用題目給的wordList是因為List跟Set在使用contains()的時間複雜度不同
wordSet會包含我們"潛在可能的所有變形字串", 若我們用過字串來當作我們的變形路程, 則會把字串移除 - levelSet: 存放這一步我們可以變形的所有字串
- nextLevelSet: 記錄下一步我們要走訪的所有字串
- level: 紀錄現在已經變形第幾次了
最一開始從beginning word 就是level 1, 因此之後如果在level x的時候拿到的字可以靠 變形一個字就找到ending word的話, 代表我們總共需要變形x+1次(因為我們還需要變形就代表這些字都是在下一level的, 因此最後回傳是回傳level+1) - curWord: 要拿來測試變形的字, 看可否變成ending word或者任何在wordSet裡面的字
是char array的原因是因為在java裡, 如果我們只想要改變某個字串的其中一個字母, 程序繁瑣(需要一直用substring,時間複雜度高), 但用char陣列的話會方便很多 - newWord: curWord在改變一個字母後 組成的新字, 當我們組成newWord後,若可以在wordSet中找到一樣的字, 我們就可以把這個新字放進nextLevelSet. 下一輪再來看他可以如何再變形
用上個例子來說, 我們可以用下圖來表示每次變形(不同層表示不同次) 來顯現當時在levelSet裡面的字有哪些
而log沒被放進第四層的原因純粹是因為我們在第四層的時候就已經找到我們可以由dog變形成cog了,因此直接回傳答案即可
以下為169ms程式碼, 贏過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;
}🚧有兩種方法可以讓上述程式碼的時間複雜度降低
🔧1. 我們用相同邏輯, 但這次用queue來取代 levelSet及每輪都會被宣告的nextLevelSet, 減少時間複雜度
以下為85ms程式碼, 贏過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. 原本我們只是在level 1的時候看beginning word要經過幾個level才會變成ending word, 但現在增加另一個set稱為backwardSet, 幫忙看endWord要經過幾個level才會變成beginWord
當backwardSet包含的字串比我們原本levelSet的字串多的時候, 就會把backwardSet 和 levelSet互換, 總之最後就會一直維持著levelSet 的字串選擇一定比backwardSet多, 且我們一直在找levelSet中的字是否可以變形成在backwardSet裡面的字
以下為75ms程式碼, 贏過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'. 或者延續上述講的同樣方法, 但多加個helper method來幫忙 也可以減少我們跑程式的時間.
以下為 55ms程式碼, 贏過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);
}
