##最小操作數 ### 題目描述 給定一個單詞集合Dict，其中每個單詞的長度都相同。現從此單詞集合Dict中抽取兩個單詞A、B，我們希望通過若干次操作把單詞A變成單詞B，每次操作可以改變單詞的一個字母，同時，新產生的單詞必須是在給定的單詞集合Dict中。求所有行得通步數最少的修改方法。 舉個例子如下： Given: A = "hit" B = "cog" Dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] 即把字符串A = "hit"轉變成字符串B = "cog"，有以下兩種可能： "hit" -> "hot" -> "dot" -> "dog" -> "cog"； "hit" -> "hot" -> "lot" -> "log" ->"cog"。 ## 分析與解法 本題是一個典型的圖搜索算法問題。此題看似跟本系列的第29章的字符串編輯距離相似，但其實區別特別大，原因是最短編輯距離是讓某個單詞增加一個字符或減少一個字符或修改一個字符達到目標單詞，來求變換的最少次數，但此最小操作數問題就只是改變一個字符。 通過[此文](http://blog.csdn.net/v_JULY_v/article/details/6111353)，我們知道，在圖搜索算法中，有深度優先遍歷DFS和廣度優先遍歷BFS，而題目中并沒有給定圖，所以需要我們自己建立圖。  涉及到圖就有這么幾個問題要思考，節點是什么？邊如何建立？圖是有方向的還是無方向的？包括建好圖之后，如何記錄單詞序列等等都是我們要考慮的問題。 ### 解法一、單向BFS法 __1__、建圖 對于本題，我們的圖的節點就是字典里的單詞，兩個節點有連邊，對應著我們可以把一個單詞按照規則變為另外一個單詞。比如我們有單詞hat，它應該與單詞cat有一條連邊，因為我們可以把h變為c，反過來我們也可以把c變為h，所以我們建立的連邊應該是無向的。 如何建圖？有兩種辦法， * 第一種方法是：我們可以把字典里的任意兩個單詞，通過循環判斷一下這兩個單詞是否只有一個位置上的字母不同。即假設字典里有n個單詞，我們遍歷任意兩個單詞的復雜度是O(n2)，如果每個單詞長度為length，我們判斷兩個單詞是否連邊的復雜度是O(length)，所以這個建圖的總復雜度是O(n2*length)。但當n比較大時，這個復雜度非常高，有沒有更好的方法呢？ * 第二種方法是：我們把字典里地每個單詞的每個位置的字母修改一下，從字典里查找一下（若用基于red-black tree的map查找，其查找復雜度為O(logn)，若用基于hashmap的unordered_map，則查找復雜度為O(1)），修改后的單詞是否在字典里出現過。即我們需要遍歷字典里地每一個單詞O(n)，嘗試修改每個位置的每個字母，對每個位置我們需要嘗試26個字母（其實是25個，因為要改得和原來不同），因此這部分復雜度是O(26*length)，總復雜度是O(26 * n * length) （第二種方法優化版：這第二種方法能否更優？在第二種方法中，我們對每個單詞每個位置嘗試了26次修改，事實上我們可以利用圖是無向的這一特點，我們對每個位置試圖把該位置的字母變到字典序更大的字母。例如，我們只考慮cat變成hat，而不考慮hat變成cat，因為再之前已經把無向邊建立了。這樣，只進行一半的修改次數，從而減少程序的運行時間。當然這個優化從復雜度上來講是常數的，因此稱為常數優化，此雖算是一種改進，但不足以成為第三種方法，原因是我們經常忽略O背后隱藏的常數）。 OK，上面兩種方法孰優孰劣呢？直接比較n2*length 與 26 * n * length的大小。很明顯，通常情況下，字典里的單詞個數非常多，也就是n比較大，因此第二種方法效果會好一些，稍后的參考代碼也會選擇上述第二種方法的優化。 __2__、記錄單詞序列 對于最簡單的bfs，我們是如何記錄路徑的？如果只需要記錄一條最短路徑的話，我們可以對每個走到的位置，記錄走到它的前一個位置。這樣到終點后，我們可以不斷找到它的前一個位置。我們利用了最短路徑的一個特點：即第二次經過一個節點的時候，路徑長度不比第一次經過它時短。因此這樣的路徑是沒有圈的。 但是本題需要記錄全部的路徑，我們第二次經過一個節點時，路徑長度可能會和第一次經過一個節點時路徑長度一樣。這是因為，我們可能在第i層中有多個節點可以到達第(i + 1)層的同一個位置，這樣那個位置有多條路徑都是最短路徑。 如何解決呢？——我們記錄經過這個位置的前面所有位置的集合。這樣一個節點的前驅不是一個節點，而是一個節點的集合。如此，當我們第二次經過一個第(i+ 1)層的位置時，我們便保留前面那第i層位置的集合作為前驅。 __3__、遍歷 解決了以上兩個問題，我們最終得到的是什么？如果有解的話，我們最終得到的是從終點開始的前一個可能單詞的集合，對每個單詞，我們都有能得到它的上一個單詞的集合，直到起點。這就是bfs分層之后的圖，我們從終點開始遍歷這個圖的到起點的所有路徑，就得到了所有的解，這個遍歷我們可以采用之前介紹的dfs方法（路徑的數目可能非常多）。 其實，為了簡單起見，我們可以從終點開始bfs，因為記錄路徑記錄的是之前的節點，也就是反向的。這樣最終可以按順序從起點遍歷到終點的所有路徑。 參考代碼如下： ```cpp //copyright@caopengcs //updated@July 08/12/2013 class Solution { public: // help 函數負責找到所有的路徑 void help(intx,vector<int> &d, vector<string> &word,vector<vector<int> > &next,vector<string> &path,vector<vector<string> > &answer) { path.push_back(word[x]); if (d[x] == 0) { //已經達到終點了 answer.push_back(path); } else { int i; for (i = 0; i <next[x].size(); ++i) { help(next[x][i],d, word, next,path,answer); } } path.pop_back(); //回溯 } vector<vector<string>> findLadders(string start, string end, set<string>& dict) { vector<vector<string> > answer; if (start == end) { //起點終點恰好相等 return answer; } //把起點終點加入字典的map dict.insert(start); dict.insert(end); set<string>::iterator dt; vector<string> word; map<string,int>allword; //把set轉換為map，這樣每個單詞都有編號了。 for (dt = dict.begin(); dt!= dict.end(); ++dt) { word.push_back(*dt); allword.insert(make_pair(*dt, allword.size())); } //建立連邊 鄰接表 vector<vector<int> > con; int i,j,n =word.size(),temp,len = word[0].length(); con.resize(n); for (i = 0; i < n; ++i) { for (j = 0; j <len; ++j) { char c; for (c =word[i][j] + 1; c <= 'z'; ++c) { //根據上面第二種方法的優化版的思路，讓每個單詞每個位置變更大 char last =word[i][j]; word[i][j] =c; map<string,int>::iterator t = allword.find(word[i]); if (t !=allword.end()) { con[i].push_back(t->second); con[t->second].push_back(i); } word[i][j] =last; } } } //以下是標準bfs過程 queue<int> q; vector<int> d; d.resize(n, -1); int from = allword[start],to = allword[end]; d[to] = 0; //d記錄的是路徑長度，-1表示沒經過 q.push(to); vector<vector<int> > next; next.resize(n); while (!q.empty()) { int x = q.front(), now= d[x] + 1; //now相當于路徑長度 //當now > d[from]時，則表示所有解都找到了 if ((d[from] >= 0)&& (now > d[from])) { break; } q.pop(); for (i = 0; i <con[x].size(); ++i) { int y = con[x][i]; //第一次經過y if (d[y] < 0) { d[y] = now; q.push(y); next[y].push_back(x); } //非第一次經過y else if (d[y] ==now) { //是從上一層經過的，所以要保存 next[y].push_back(x); } } } if (d[from] >= 0) { //有解 vector<string>path; help(from, d,word,next, path,answer); } return answer; } }; ``` ### 解法二、雙向BFS法 BFS需要把每一步搜到的節點都存下來，很有可能每一步的搜到的節點個數越來越多，但最后的目的節點卻只有一個。后半段的很多搜索都是白耗時間了。 上面給出了單向BFS的解法，但看過此前blog中的這篇文章[“A*、Dijkstra、BFS算法性能比較演示”](http://blog.csdn.net/v_JULY_v/article/details/6238029)可知：雙向BFS性能優于單向BFS。 舉個例子如下，第1步，是起點，1個節點，第2步，搜到2個節點，第3步，搜到4個節點，第4步搜到8個節點，第5步搜到16個節點，并且有一個是終點。那這里共出現了31個節點。從起點開始廣搜的同時也從終點開始廣搜，就有可能在兩頭各第3步，就相遇了，出現的節點數不超過(1+2+4)*2=14個，如此就節省了一半以上的搜索時間。 下面給出雙向BFS的解法，參考代碼如下： ```cpp //copyright@fuwutu 6/26/2013 class Solution { public: vector<vector<string>> findLadders(string start, string end, set<string>& dict) { vector<vector<string>> result; if (dict.erase(start) == 1 && dict.erase(end) == 1) { map<string, vector<string>> kids_from_start; map<string, vector<string>> kids_from_end; set<string> reach_start; reach_start.insert(start); set<string> reach_end; reach_end.insert(end); set<string> meet; while (meet.empty() && !reach_start.empty() && !reach_end.empty()) { if (reach_start.size() < reach_end.size()) { search_next_reach(reach_start, reach_end, meet, kids_from_start, dict); } else { search_next_reach(reach_end, reach_start, meet, kids_from_end, dict); } } if (!meet.empty()) { for (set<string>::iterator it = meet.begin(); it != meet.end(); ++it) { vector<string> words(1, *it); result.push_back(words); } walk(result, kids_from_start); for (size_t i = 0; i < result.size(); ++i) { reverse(result[i].begin(), result[i].end()); } walk(result, kids_from_end); } } return result; } private: void search_next_reach(set<string>& reach, const set<string>& other_reach, set<string>& meet, map<string, vector<string>>& path, set<string>& dict) { set<string> temp; reach.swap(temp); for (set<string>::iterator it = temp.begin(); it != temp.end(); ++it) { string s = *it; for (size_t i = 0; i < s.length(); ++i) { char back = s[i]; for (s[i] = 'a'; s[i] <= 'z'; ++s[i]) { if (s[i] != back) { if (reach.count(s) == 1) { path[s].push_back(*it); } else if (dict.erase(s) == 1) { path[s].push_back(*it); reach.insert(s); } else if (other_reach.count(s) == 1) { path[s].push_back(*it); reach.insert(s); meet.insert(s); } } } s[i] = back; } } } void walk(vector<vector<string>>& all_path, map<string, vector<string>> kids) { vector<vector<string>> temp; while (!kids[all_path.back().back()].empty()) { all_path.swap(temp); all_path.clear(); for (vector<vector<string>>::iterator it = temp.begin(); it != temp.end(); ++it) { vector<string>& one_path = *it; vector<string>& p = kids[one_path.back()]; for (size_t i = 0; i < p.size(); ++i) { all_path.push_back(one_path); all_path.back().push_back(p[i]); } } } } }; ```