題目描述
這是 LeetCode 上的 「127. 單詞接龍」 靶溜，難度為 「困難」已艰。
Tag : 「雙向 BFS」
字典 wordList 中從單詞 beginWord 和 endWord 的 轉(zhuǎn)換序列 是一個按下述規(guī)格形成的序列：
- 序列中第一個單詞是 beginWord 。
- 序列中最后一個單詞是 endWord 顽素。
- 每次轉(zhuǎn)換只能改變一個字母讯屈。
- 轉(zhuǎn)換過程中的中間單詞必須是字典 wordList 中的單詞。
給你兩個單詞 beginWord 和 endWord 和一個字典 wordList 嚎于，找到從 beginWord 到 endWord 的「最短轉(zhuǎn)換序列」中的「單詞數(shù)目」。
如果不存在這樣的轉(zhuǎn)換序列昼伴，返回 0匾旭。
示例 1：
輸入：beginWord =?"hit",?endWord?=?"cog",?wordList?=?["hot","dot","dog","lot","log","cog"]
輸出：5
解釋：一個最短轉(zhuǎn)換序列是?"hit"?->?"hot"?->?"dot"?->?"dog"?->?"cog", 返回它的長度 5镣屹。示例 2：
輸入：beginWord =?"hit",?endWord?=?"cog",?wordList?=?["hot","dot","dog","lot","log"]
輸出：0
解釋：endWord "cog"?不在字典中圃郊，所以無法進行轉(zhuǎn)換。提示：
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord女蜈、endWord 和 wordList[i] 由小寫英文字母組成
- beginWord != endWord
- wordList 中的所有字符串 互不相同
基本分析
根據(jù)題意持舆，每次只能替換一個字符，且每次產(chǎn)生的新單詞必須在 wordList 出現(xiàn)過伪窖。
一個樸素的實現(xiàn)方法是逸寓，使用 BFS 的方式求解:
從 beginWord 出發(fā)，枚舉所有替換一個字符的方案覆山，如果方案存在于 wordList 中竹伸，則加入隊列中，這樣隊列中就存在所有替換次數(shù)為 的單詞簇宽。
然后從隊列中取出元素勋篓，繼續(xù)這個過程，直到遇到 endWord 或者隊列為空為止 ...
同時為了「防止重復(fù)枚舉到某個中間結(jié)果」和「記錄每個中間結(jié)果是經(jīng)過多少次轉(zhuǎn)換而來」魏割，我們需要建立一個「哈希表」進行記錄譬嚣。
哈希表的 KV 形式為 {單詞:由多少次轉(zhuǎn)換得到}。
當(dāng)枚舉到新單詞 str 時钞它，需要先檢查是否已經(jīng)存在與「哈希表」中拜银，如果不存在則更新「哈希表」并將新單詞放入隊列中。
這樣的做法可以確痹舛猓「枚舉到所有由 beginWord 到 endWord 的轉(zhuǎn)換路徑」尼桶，并且由 beginWord 到 endWord 的「最短轉(zhuǎn)換路徑」必然會最先被枚舉到。
雙向 BFS
經(jīng)過分析锯仪，BFS 確實可以做疯汁，但本題的數(shù)據(jù)范圍較大：
樸素的 BFS 可能會引發(fā)「搜索空間爆炸」的問題。
想象一下卵酪，如果我們的 wordList 足夠豐富（包含了所有單詞）幌蚊，對于一個長度為 的 beginWord 替換一次字符可以產(chǎn)生 個新單詞（每個替換點可以替換另外 個小寫字母）谤碳，第一層就會產(chǎn)生 個單詞；第二層會產(chǎn)生超過 個新單詞 ...
隨著層數(shù)的加深溢豆，這個數(shù)字的增速越快蜒简，這就是「搜索空間爆炸」問題。
在樸素的 BFS 實現(xiàn)中漩仙，空間的瓶頸主要取決于搜索空間中的最大寬度搓茬。
那么有沒有辦法讓我們不使用這么寬的搜索空間，同時又能保證搜索到目標結(jié)果呢队他？
「雙向 BFS」 可以很好的解決這個問題：
同時從兩個方向開始搜索卷仑，一旦搜索到相同的值，意味著找到了一條聯(lián)通起點和終點的最短路徑麸折。
「雙向 BFS」的基本實現(xiàn)思路如下：
- 創(chuàng)建「兩個隊列」分別用于兩個方向的搜索锡凝；
- 創(chuàng)建「兩個哈希表」用于「解決相同節(jié)點重復(fù)搜索」和「記錄轉(zhuǎn)換次數(shù)」；
- 為了盡可能讓兩個搜索方向“平均”垢啼，每次從隊列中取值進行擴展時窜锯，先判斷哪個隊列容量較少；
- 如果在搜索過程中「搜索到對方搜索過的節(jié)點」芭析，說明找到了最短路徑锚扎。
「雙向 BFS」基本思路對應(yīng)的偽代碼大致如下：
d1、d2?為兩個方向的隊列
m1馁启、m2?為兩個方向的哈希表驾孔，記錄每個節(jié)點距離起點的
????
//?只有兩個隊列都不空，才有必要繼續(xù)往下搜索
//?如果其中一個隊列空了惯疙，說明從某個方向搜到底都搜不到該方向的目標節(jié)點
while(!d1.isEmpty()?&&?!d2.isEmpty())?{
????if?(d1.size()?<?d2.size())?{
????????update(d1,?m1,?m2);
????}?else?{
????????update(d2,?m2,?m1);
????}
}
//?update?為從隊列?d?中取出一個元素進行「一次完整擴展」的邏輯
void?update(Deque?d,?Map?cur,?Map?other)?{}回到本題翠勉，我們看看如何使用「雙向 BFS」進行求解。
估計不少同學(xué)是第一次接觸「雙向 BFS」螟碎，因此這次我寫了大量注釋眉菱。
建議大家?guī)е鴮Α鸽p向 BFS」的基本理解去閱讀。
代碼：
class?Solution?{
????String?s,?e;
????Set<String>?set?=?new?HashSet<>();
????public?int?ladderLength(String?_s,?String?_e,?List<String>?ws)?{
????????s?=?_s;
????????e?=?_e;
????????//?將所有?word?存入?set掉分，如果目標單詞不在?set?中俭缓，說明無解
????????for?(String?w?:?ws)?set.add(w);
????????if?(!set.contains(e))?return?0;
????????int?ans?=?bfs();
????????return?ans?==?-1???0?:?ans?+?1;
????}
????int?bfs()?{
????????//?d1?代表從起點?beginWord?開始搜索（正向）
????????//?d2?代表從結(jié)尾?endWord?開始搜索（反向）
????????Deque<String>?d1?=?new?ArrayDeque<>(),?d2?=?new?ArrayDeque();?
????????
????????/*
?????????*?m1?和?m2?分別記錄兩個方向出現(xiàn)的單詞是經(jīng)過多少次轉(zhuǎn)換而來
?????????*?e.g.?
?????????*?m1?=?{"abc":1}?代表?abc?由?beginWord?替換?1?次字符而來
?????????*?m1?=?{"xyz":3}?代表?xyz?由?endWord?替換?3?次字符而來?????????*/
????????Map<String,?Integer>?m1?=?new?HashMap<>(),?m2?=?new?HashMap<>();
????????d1.add(s);
????????m1.put(s,?0);
????????d2.add(e);
????????m2.put(e,?0);
????????
????????/*
?????????*?只有兩個隊列都不空，才有必要繼續(xù)往下搜索
?????????*?如果其中一個隊列空了酥郭，說明從某個方向搜到底都搜不到該方向的目標節(jié)點
?????????*?e.g.?
?????????*?例如华坦，如果?d1?為空了，說明從?beginWord?搜索到底都搜索不到?endWord不从，反向搜索也沒必要進行了?????????*/
????????while?(!d1.isEmpty()?&&?!d2.isEmpty())?{
????????????int?t?=?-1;
????????????//?為了讓兩個方向的搜索盡可能平均惜姐，優(yōu)先拓展隊列內(nèi)元素少的方向
????????????if?(d1.size()?<=?d2.size())?{
????????????????t?=?update(d1,?m1,?m2);
????????????}?else?{
????????????????t?=?update(d2,?m2,?m1);
????????????}
????????????if?(t?!=?-1)?return?t;
????????}
????????return?-1;
????}
????//?update?代表從?deque?中取出一個單詞進行擴展，
????// cur 為當(dāng)前方向的距離字典；other 為另外一個方向的距離字典
????int?update(Deque<String>?deque,?Map<String,?Integer>?cur,?Map<String,?Integer>?other)?{
????????//?獲取當(dāng)前需要擴展的原字符串
????????String?poll?=?deque.pollFirst();
????????int?n?=?poll.length();
????????//?枚舉替換原字符串的哪個字符?i
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????//?枚舉將?i?替換成哪個小寫字母
????????????for?(int?j?=?0;?j?<?26;?j++)?{
????????????????//?替換后的字符串
????????????????String?sub?=?poll.substring(0,?i)?+?String.valueOf((char)('a'?+?j))?+?poll.substring(i?+?1);
????????????????if?(set.contains(sub))?{
????????????????????//?如果該字符串在「當(dāng)前方向」被記錄過（拓展過）歹袁，跳過即可
????????????????????if?(cur.containsKey(sub))?continue;
????????????????????//?如果該字符串在「另一方向」出現(xiàn)過坷衍，說明找到了聯(lián)通兩個方向的最短路
????????????????????if?(other.containsKey(sub))?{
????????????????????????return?cur.get(poll)?+?1?+?other.get(sub);
????????????????????}?else?{
????????????????????????//?否則加入?deque?隊列
????????????????????????deque.addLast(sub);
????????????????????????cur.put(sub,?cur.get(poll)?+?1);
????????????????????}
????????????????}
????????????}
????????}
????????return?-1;
????}
}- 時間復(fù)雜度：令
wordList長度為 ，beginWord字符串長度為 条舔。由于所有的搜索結(jié)果必須都在wordList出現(xiàn)過枫耳，因此算上起點最多有 節(jié)點，最壞情況下孟抗，所有節(jié)點都聯(lián)通迁杨，搜索完整張圖復(fù)雜度為 ；從beginWord出發(fā)進行字符替換凄硼，替換時進行逐字符檢查铅协，復(fù)雜度為 。整體復(fù)雜度為 - 空間復(fù)雜度：同等空間大小摊沉。
總結(jié)
這本質(zhì)其實是一個「所有邊權(quán)均為 1」最短路問題：將 beginWord 和所有在 wordList 出現(xiàn)過的字符串看做是一個點狐史。每一次轉(zhuǎn)換操作看作產(chǎn)生邊權(quán)為 1 的邊。問題求以 beginWord 為源點坯钦，以 endWord 為匯點的最短路徑预皇。
借助這個題侈玄，我向你介紹了「雙向 BFS」婉刀，「雙向 BFS」可以有效解決「搜索空間爆炸」問題。
對于那些搜索節(jié)點隨著層數(shù)增加呈倍數(shù)或指數(shù)增長的搜索問題序仙，可以使用「雙向 BFS」進行求解突颊。
最后
這是我們「刷穿 LeetCode」系列文章的第 No.127 篇，系列開始于 2021/01/01潘悼，截止于起始日 LeetCode 上共有 1916 道題目律秃，部分是有鎖題，我們將先將所有不帶鎖的題目刷完治唤。
在這個系列文章里面棒动，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼宾添。如果涉及通解還會相應(yīng)的代碼模板船惨。
為了方便各位同學(xué)能夠電腦上進行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 缕陕。
在倉庫地址里粱锐，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼扛邑、LeetCode 原題鏈接和其他優(yōu)選題解怜浅。
本文使用 文章同步助手 同步
