BFS ---- 再磕時間複雜度

11.13

更新雙向 BFS ，具體參見第 3 部分。感謝評論區提醒。

第 4 部分多源 BFS 待補充，歡迎投稿。

今天刷到了道頗有性格的演算法題，分享於此，諸君共勉。

1. 題目：

單詞接龍

給出兩個單詞（start和end）和一個字典，找到從start到end的最短轉換序列

注意：

1. 每次只能改變一個字母。
2. 變換過程中的中間單詞必須在字典中出現。
3. 如果沒有轉換序列則返回0。
4. 所有單詞具有相同的長度。
5. 所有單詞都只包含小寫字母。

樣例：

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

一個最短的變換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，

返回它的長度 5

2. 分析

以往做 BFS 的題目都是樹、圖，這道題在其外加上單詞接龍的蓋頭，初看的確是略微懵逼。好在我是在 BFS 專項訓練中遇到這道題，順著 BFS 的線索，總算略窺門徑。

BFS 的根本思想是由近到遠、逐層遍歷，由此可以解決我們經常遇到的求最短路徑問題。其實如果演算法敏感性較高，看到題目「最短」兩字應該有 BFS 的想法。回到本題，「每次只能改變一個字母，變換過程中的中間單詞必須在字典中出現。」，十分類似於我們在用 BFS 遍歷圖時找鄰居的感覺。至此，脫掉這道題的衣服啊不偽裝，發現其內在就是一個由近到遠、分層遍歷的 BFS 。

所以，提筆就是一套典型的 BFS ：

class Solution {npublic:n /*n * @param start: a stringn * @param end: a stringn * @param dict: a set of stringn * @return: An integern */n int ladderLength(string &start, string &end, unordered_set<string> &dict) {n // write your code heren int step = 0;n const int INF = 1000000;n if (dict.empty() || start.empty() || end.empty()) {n return step;n }n //map<string, set<string>> neighbors = getNeighbors(dict);n map<string, int> distance;n for (auto s : dict) {n distance.insert(pair<string, int>(s, INF));n }nn queue<string> que;n que.push(start);n n while (!que.empty()) {n step++;n int len = que.size();n for (int i = 0; i < len; i++) {n string now = que.front();n que.pop();n if (isNeighbor(now, end)) {n return (step + 1);n }n distance[now] = step;n for (string nbor : getNeighbors(now, dict, distance, INF)) {n que.push(nbor);n }n }n }n return 0;n }nprivate:n set<string> getNeighbors(string str, unordered_set<string> &dict,n map<string, int> distance, int INF) {n set<string> result;n for (auto s : dict) {n if (isNeighbor(s, str) && distance[s] == INF) {n result.insert(s);n }n }n return result;n }n bool isNeighbor(string s1, string s2) {n int dist = 0;n for (int i = 0; i < s1.size(); i++) {n if (s1[i] != s2[i]) {n dist++;n }n }n return (dist == 1);n }n};n

點擊運行，60% 測試樣例通過後報超時。

分析目前代碼的時間複雜度，核心部分是 while 循環，時間複雜度 ，其中 n 為 dict 長度。

2.1 改進

分析這個複雜度，最外層的 肯定是不可改進的，能改進的只能是 getNeighbors() 部分。目前每出隊一個詞語，都要和 dict 內所有詞語做 inNeighbor 比較，時間複雜度是 。從報錯的測試樣例來看，dict 內字元串的長度一般都很短，所以該 getNeighbors 為 makeNeighbors，然後將 make 的所有鄰居與 dict 比較。dict 是 set ，比較查詢只有 ，關鍵看 makeNeighbors 的複雜度了，修改代碼如下：

class Solution {npublic:n /*n * @param start: a stringn * @param end: a stringn * @param dict: a set of stringn * @return: An integern */n int ladderLength(string &start, string &end, unordered_set<string> &dict) {n // write your code heren int step = 0;n const int INF = 1000000;n dict.insert(end);n cout<<dict.size()<<endl;n if (dict.empty() || start.empty() || end.empty()) {n return step;n }n // O(n^2 * mean_strlen)n n //map<string, set<string>> neighbors = getNeighbors(start, end, dict);n //cout<<"12"<<endl;n unordered_map<string, int> distance;n for (auto s : dict) {n distance.insert(pair<string, int>(s, INF));n }n n queue<string> que;n que.push(start);n cout<<"1"<<endl;n int c=0;n while (!que.empty()) {n step++;n int len = que.size();n cout<<step<<endl;n cout<<"count: "<<c<<endl;nn for (int i = 0; i < len; i++) {n string now = que.front();n que.pop();n c++;n if (now == end) {n return step;n }n distance[now] = step;n n // O(mean_neighbors)n for (string nbor : makeNeighbors(now)) {n if (dict.find(nbor) != dict.end()) {n if (distance[nbor] == INF) {n que.push(nbor);n }n }n n }n }n }n return 0;n }nprivate:n set<string> makeNeighbors(string s) {n set<string> result;n int len = s.size();n string chars = "qwertyuiopasdfghjklzxcvbnm";n for (int i = 0; i < len; i++) {n for (char c : chars) {n result.insert(s.substr(0, i) + c + s.substr(i+1, len - i - 1));n }n n }n return result;n }n};n

makeNeighbors 為 ，整體為 ，樣本較多時，n 遠大於 26 ，因此可以顯著降低時間複雜度。

運行 ----> 依舊超時。。。。

2.2 再次改進

改進仍然應專註於 while 內的第二個 for 。

由於我們將 distance 的改進置於 while 內第二個 for 之後，while 內最後一行 que.push(nbor) 並不能更新 distance ，導致第二個 for 會重複添加進 nbor（因為判斷當前 nbor 是否應更新的依據是 distance 是否有過改變） ，因此本次改進應將 distance 的更新置於第二個 for 內部。

最終代碼如下：

class Solution {npublic:n /*n * @param start: a stringn * @param end: a stringn * @param dict: a set of stringn * @return: An integern */n int ladderLength(string &start, string &end, unordered_set<string> &dict) {n // write your code heren int step = 0;n const int INF = 1000000;n dict.insert(end);n if (dict.empty() || start.empty() || end.empty()) {n return step;n }n // O(n^2 * mean_strlen)n n //map<string, set<string>> neighbors = getNeighbors(start, end, dict);n //cout<<"12"<<endl;n unordered_map<string, int> distance;n for (auto s : dict) {n distance.insert(pair<string, int>(s, INF));n }n n queue<string> que;n que.push(start);n distance[start] = step;n int c=0;n while (!que.empty()) {n step++;n int len = que.size();n for (int i = 0; i < len; i++) {n string now = que.front();n que.pop();n c++;n if (now == end) {n return step;n }n for (string nbor : makeNeighbors(now)) {n if (dict.find(nbor) != dict.end()) {n if (distance[nbor] == INF) {n que.push(nbor);n distance[nbor] = step;n }n }n n }n }n }n return 0;n }nprivate:n set<string> makeNeighbors(string s) {n set<string> result;n int len = s.size();n string chars = "qwertyuiopasdfghjklzxcvbnm";n for (int i = 0; i < len; i++) {n for (char c : chars) {n result.insert(s.substr(0, i) + c + s.substr(i+1, len - i - 1));n }n n }n return result;n }n};n

3. 雙向 BFS

經評論區提醒，嘗試用雙向 BFS 解此題，才發現第 2 部分的做法真的是邪魔歪道。

首先本題（word ladder）確是一個經典題目，用雙向 BFS 解此題確是經典解法。所謂雙向，是指將經典 BFS 從起點搜到終點的單個隊列變換為從起點、終點開始兩個方向兩個隊列，每個隊列中存的是該方向目前狀態層（即同一距離）的鄰居。每次選擇鄰居較少的隊列進行更新，使得每次面對較少的選項，速度可以更快。

本題的代碼實現如下，使用 set 替代了 queue，實測發現在本題的測試樣例情況下，速度要比之前的方法快一倍。

int ladderLength(string &start, string &end, unordered_set<string> &dict) {n // write your code heren if (start.empty() || start.empty() || dict.empty()) {n return 0;n }n if (start == end) {n return 1;n }n unordered_set<string> _dict;n for (auto d : dict) {n _dict.insert(d);n }n unordered_set<string> q1, q2, tmp;n q1.insert(start);n q2.insert(end);n int count = 0;n while (!q1.empty() || !q2.empty()) {n count++;n if (q1.size() < q2.size()) {n swap(q1, q2);n }n tmp.clear();n for (string str : q1) {n for (int i = 0; i < str.size(); i++) {n char t = str[i];n for (char c = a; c <= z; c++) {n str[i] = c;n if (q2.find(str) != q2.end()) {n return ++count;n }n if (_dict.find(str) != _dict.end()) {n tmp.insert(str);n _dict.erase(str);n }n }n str[i] = t;n }n }n swap(q1, tmp);n }n}n

4. 多源 BFS

「廣告位招租，歡迎多源 BFS 投稿」

5. 鳴謝及總結

特別鳴謝 @MagicBubble ，第二部分後兩版代碼的改進基本都源於 Bubble 女士的靈感迸發，為人類的解放事業做出了不可磨滅的貢獻！

遇到本題之前，做了好幾道 BFS 的題目，有些也頗有巧思，當時自認為對 BFS 的感覺還可以，直到遇到本題。。。。

2.1 的改進當屬巧思，意義重大但不能要求時時想到。而 2.2 的改進則應該是對 BFS 有較深理解後自然應當想到的。之前一直對已遍歷過的元素的更新沒有過多注意，今天栽在這裡確實是頗有意義的，因此要始終注意元素更新位置。

當時分析出本題要用 BFS 來解決，已經覺得這道題頗為別緻，直到真正死磕時間複雜度到底，才算真的感受到「你大爺終究是你大爺」。

大爺，來兩斤 BFS ？