127. Word Ladder
文章目錄
- 1 題目理解
- 2 BFS
- 3 雙向BFS
1 題目理解
給定兩個單詞（beginWord 和 endWord）和一個字典，找到從 beginWord 到 endWord 的最短轉換序列的長度。轉換需遵循如下規則：
每次轉換只能改變一個字母。
轉換過程中的中間單詞必須是字典中的單詞。
說明:
如果不存在這樣的轉換序列，返回 0。
所有單詞具有相同的長度。
所有單詞只由小寫字母組成。
字典中不存在重復的單詞。
你可以假設 beginWord 和 endWord 是非空的，且二者不相同。
輸入：兩個單詞：beginWord,endWord，一個字典
規則：查找從beginWord到endWord的最短轉換序列。轉換中每次只能變一個字母。轉換過程中的單詞必須是字典中的單詞。
輸出：最短序列長度，沒有就返回0。
輸入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
輸出: 5
解釋: 一個最短轉換序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的長度 5。
2 BFS
解法內容來源于力扣。
要求最短序列，想到要用bfs。想到bfs，自然想到圖。題目中的圖是隱形的。我們可以抽象出圖。
可以將所有單詞抽象為一個節點。如果兩個單詞之間只有一個字母不同，則這兩個單詞之間有條邊。邊是雙向的。
例子中的圖是這樣的。我們以beginWord為起點，endWord為終點，找到最短路徑。
在建圖過程中，按照普通想法，我們可以枚舉每一對詞語，看他們是否相差一個字符。但這樣效率太低，我們可以優化圖。我們可以建一個虛擬節點。對于單詞hit創建3個虛擬節點：it,ht,hi*。hit與這三個節點有雙向邊。如果詞典中有一個單詞能夠轉為hi這種格式，那必然它也與hi有條雙向邊。
最后注意bfs找到最短路徑之后，因為加入了虛擬節點所以路徑長度需要除以2。
class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {if(wordList==null || !wordList.contains(endWord)){return 0;}Map<String,List<String>> allComboDict = new HashMap<String,List<String>>();addToDict(beginWord,allComboDict);for(String w : wordList){addToDict(w,allComboDict);}Queue<String> queue = new LinkedList<String>();queue.offer(beginWord);int step = 0;Map<String,Boolean> visited = new HashMap<String,Boolean>();while(!queue.isEmpty()){step++;int size = queue.size();for(int i=0;i<size;i++){String node = queue.poll();if(node.equals(endWord)){return step/2+1;}for(String toNode: allComboDict.get(node)){if(!visited.containsKey(toNode)){visited.put(toNode,true);queue.offer(toNode);}}}}return 0;}private void addToDict(String word,Map<String,List<String>> allComboDict ){char[] array = word.toCharArray();List<String> listOfWord = allComboDict.getOrDefault(word,new ArrayList<String>());for(int i=0;i<word.length();i++){char ch = array[i];array[i] = '*';String text = new String(array);List<String> list = allComboDict.getOrDefault(text,new ArrayList<String>());list.add(word);allComboDict.put(text,list);listOfWord.add(text);array[i] = ch;}allComboDict.put(word,listOfWord);} }時間復雜度:O(w?l2)O(w*l^2)O(w?l2)，w是單詞個數，l是每個單詞的長度。
建圖過程中，對于每個單詞需要枚舉它連接到的所有虛擬節點，復雜度為O(w)，每個單詞的長度為l，復雜度為O(wl)。
bfs過程中每個節點最多有l條邊。所以最終時間復雜度O(wl*l)。
3 雙向BFS
根據給定字典構造的圖可能會很大。BFS的搜索空間會依賴每層的分支數量增加而指數級增加。如果同時使用兩個廣度優先搜索。一個從beginWord開始搜索，一個從endWord開始搜索。每次從兩邊各擴展一層節點，當發現某一時刻，兩邊都訪問過同一節點時，就停止搜索。
總結
以上是生活随笔為你收集整理的127. Word Ladder的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： keeplive使用
- 下一篇： AMEsim fatal error U