程序員編程藝術

程序員編程藝術-最小操作數(shù)問題作者：July、caopengcs、紅色標記。致謝：fuwutu、demo。時間：二零一三年八月十二日題目詳情如下：給定一個單詞集合Diet，其中每個單詞的長度都相同?，F(xiàn)從此單詞集合Diet中抽取兩個單詞A、B,我們希望通過若干次操作把單詞A變成單詞B,每次操作可以改變單詞的一個字母，同時，新產(chǎn)生的單詞必須是在給定的單詞集合Diet中。求所有行得通步數(shù)最少的修改方法。舉個例子如下：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章的字符串編輯距離相似，但其實區(qū)別特別大，原因是最短編輯距離是讓某個單詞增加一個字符或減少一個字符或修改一個字符達到目標單詞，來求變換的最少次數(shù)，但此最小操作數(shù)問題就只是改變一個字符。我們知道，在圖搜索算法中，有深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS，而題目中并

hit■hothit■hot第1層:第2層:第3層:第5層:第第5層:涉及到圖就有這么幾個問題要思考，節(jié)點是什么？邊如何建立？圖是有方向的還是無方向的？包括建好圖之后，如何記錄單詞序列等等都是我們要考慮的問題。解法一、單向BFS法1、建圖對于本題，我們的圖的節(jié)點就是字典里的單詞，兩個節(jié)點有連邊，對應著我們可以把一個單詞按照規(guī)則變?yōu)榱硗庖粋€單詞。比如我們有單詞hat，它應該與單詞cat有一條連邊，因為我們可以把h變?yōu)閏,反過來我們也可以把c變?yōu)閔,所以我們建立的連邊應該是無向的。如何建圖？有兩種辦法，?第一種方法是：我們可以把字典里的任意兩個單詞，通過循環(huán)判斷一下這兩個單詞是否只有一個位置上的字母不同。即假設字典里有n個單詞，我們遍歷任意兩個單詞的復雜度是0(n2)，如果每個單詞長度為length，我們判斷兩個單詞是否連邊的復雜度是0(length),所以這個建圖的總復雜度是0(n2*length)。但當n比較大時，這個復雜度非常高，有沒有更好的方法呢？?第二種方法是：我們把字典里地每個單詞的每個位置的字母修改一下，從字典里查找一下(若用基于red-blacktree的map查找，其查找復雜度為O(logn),若用基于hashmap的unordered_map,則查找復雜度為0(1))，修改后的單詞是否在字典里出現(xiàn)過。即我們需要遍歷字典里地每一個單詞0(n),嘗試修改每個位置的每個字母，對每個位置我們需要嘗試26個字母(其實是25個，因為要改得和原來不同)，因此這部分復雜度是O(26*length),總復雜度是0(26*n*length)(第二種方法優(yōu)化版：這第二種方法能否更優(yōu)？在第二種方法中，我們對每個單詞每個位置嘗試了26次修改，事實上我們可以利用圖是無向的這一特點，我們對每個位置試圖把該位置的字母變到字典序更大的字母。例如，我們只考慮cat變成hat，而不考慮hat變成cat，因為再之前已經(jīng)把無向邊建立了。這樣，只進行一半的修改次數(shù)，從而減少程序的運行時間。當然這個優(yōu)化從復雜度上來講是常數(shù)的，因此稱為常數(shù)優(yōu)化，此雖算是一種改進，但不足以成為第三種方法，原因是我們經(jīng)常忽略O背后隱藏的常數(shù))。0K,上面兩種方法孰優(yōu)孰劣呢？直接比較n2*length與26*n*length的大小。很明顯，通常情況下，字典里的單詞個數(shù)非常多，也就是n比較大，因此第二種方法效果會好一些，稍后的參考代碼也會選擇上述第二種方法的優(yōu)化。2、 記錄單詞序列對于最簡單的bfs,我們是如何記錄路徑的？如果只需要記錄一條最短路徑的話，我們可以對每個走到的位置，記錄走到它的前一個位置。這樣到終點后，我們可以不斷找到它的前一個位置。我們利用了最短路徑的一個特點：即第二次經(jīng)過一個節(jié)點的時候，路徑長度不比第一次經(jīng)過它時短。因此這樣的路徑是沒有圈的。但是本題需要記錄全部的路徑，我們第二次經(jīng)過一個節(jié)點時，路徑長度可能會和第一次經(jīng)過一個節(jié)點時路徑長度一樣。這是因為，我們可能在第i層中有多個節(jié)點可以到達第(i+1)層的同一個位置，這樣那個位置有多條路徑都是最短路徑。如何解決呢？一一我們記錄經(jīng)過這個位置的前面所有位置的集合。這樣一個節(jié)點的前驅不是一個節(jié)點，而是一個節(jié)點的集合。如此，當我們第二次經(jīng)過一個第(i+1)層的位置時，我們便保留前面那第i層位置的集合作為前驅。3、 遍歷解決了以上兩個問題，我們最終得到的是什么？如果有解的話，我們最終得到的是從終點開始的前一個可能單詞的集合，對每個單詞，我們都有能得到它的上一個單詞的集合，直到起點。這就是bfs分層之后的圖，我們從終點開始遍歷這個圖的到起點的所有路徑，就得到了所有的解，這個遍歷我們可以采用之前介紹的dfs方法(路徑的數(shù)目可能非常多)。其實，為了簡單起見，我們可以從終點開始bfs，因為記錄路徑記錄的是之前的節(jié)點，也就是反向的。這樣最終可以按順序從起點遍歷到終點的所有路徑。參考代碼如下:

//copyright@caopengcs//updated@July08/12/2013classSolution{public://help函數(shù)負責找到所有的路徑voidhelp(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){ //已經(jīng)達到終點了answer.push_back(path);}else{inti;for(i=0;i<next[x].size();++i){help(next[x][i],d,word,next,path,answer);}}path.pop_back();//回溯set<string>&set<string>&vector<vector<string>>findLadders(stringstart,stringend,{vector<vector<string>>answer;if(start==end){ //起點終點恰好相等returnanswer;}//把起點終點加入字典的mapdict.insert(start);dict.insert(end);set<string>::iteratordt;vector<string>word;map<stringint>allword;//把set轉換為map，這樣每個單詞都有編號了。for(dt=dict.begin();dt!=dict.end();++dt){word.push_back(*dt);allword.insert(make_pair(*dt,allword.size()));}//建立連邊鄰接表vector<vectorint>>con;89101112131415161718192021diet)222324252627282930313233343536373839404142inti,j,n=word.size(),temp,len=word[0].length();43444546con.resize(n);for(i=0;i<n;++i){for(j=0;j<len;++j){charc;for(c=word[i][j]+1;c<='z';++c){ //根據(jù)上面第二種方法的47優(yōu)化版的思路，讓每個單詞每個位置變更大4849505152535455565758596061626364656667686970717273747576777879808182838485charlast=word[i][j];word[i][j]=c;map<strinint>::iteratort=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過程queueint>q;vectorint>d;d.resize(n,-1);intfrom=allword[start],to=allword[end];d[to]=0;//d記錄的是路徑長度，-1表示沒經(jīng)過q.push(to);vector<vectorint>>next;next.resize(n);while(!q.empty()){intx=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){inty=con[x][i];//第一次經(jīng)過yif(d[y]<0){d[y]=now;q.push(y);next[y].push_back(x);}8687//非第一次經(jīng)過yelse88if(d[y]==now){ //是從上一層經(jīng)過的，所以要保存next[y].push_back(x);8990919293}}if(d[from]>=0){//有解9495969798vector<string>path;help(from,d,word,next,path,answer);}returnanswer;}99｝；解法二、雙向BFS法BFS需要把每一步搜到的節(jié)點都存下來，很有可能每一步的搜到的節(jié)點個數(shù)越來越多,但最后的目的節(jié)點卻只有一個。后半段的很多搜索都是白耗時間了。上面給出了單向BFS的解法，但是實際上雙向BFS性能優(yōu)于單向BFS。舉個例子如下，第1步，是起點，1個節(jié)點，第2步，搜到2個節(jié)點，第3步，搜到4個節(jié)點，第4步搜到8個節(jié)點，第5步搜到16個節(jié)點，并且有一個是終點。那這里共出現(xiàn)了31個節(jié)點。從起點開始廣搜的同時也從終點開始廣搜，就有可能在兩頭各第3步，就相遇了，出現(xiàn)的節(jié)點數(shù)不超過(1+2+4)*2=14個，如此就節(jié)省了一半以上的搜索時間。下面給出雙向BFS的解法，參考代碼如下：//copyright@fuwutu6/26/2013classSolutionTOC\o"1-5"\h\z{public:vector<vector<string>>findLadders(stringstart,stringend,set<string>&dict){vector<vector<string>>result,result_temp;if(dict.erase(start)==1&&dict.erase(end)==1){map<string, vector<string>> kids_from_start;map<string, vector<string>> kids_from_end;111set<string> reach_start;reach_start.insert(start);127127128129130131132++it)133134135136137138139140141142143144145146147148114set<string>reach_end;115116reach_end.insert(end);117set<string>meet;118while(meet.empty()&&!reach_start.empty()&&!reach_end.empty())119{120if(reach_start.size()<reach_end.size())121{122search_next_reach(reach_start,reach_end,meet,kids_from_start,diet);123}124else125{126search_next_reach(reach_end,reaeh_start,meet,126kids_from_end,diet);}}if(!meet.empty()){for(set<string>::iteratorit=meet.begin();it!=meet.end();{vector<string>words(1,*it);result.push_back(words);}walk(result,kids_from_start);for(size_ti=0;i<result.size();++i){reverse(result[i].begin(),result[i].end());}walk(result,kids_from_end);}}returnresult;}149private:voidsearch_next_reach(set<string>&reach,constset<string>&other_reach,set<string>&meet,map<string,vector<string>>&path,set<string>&dict)153set<string>temp;154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188kids)189190191192193194195reach.swap(temp);for(set<string>::iteratorit=temp.begin();it!=temp.end();++it){strings=*it;for(size_ti=0;i<s.length();++i){charback=s[i];for(s[i]='a';s[i]<='z';++s[i]){if(s[i]!=back){if(re