程序員編程藝術(shù)

程序員編程藝術(shù)-最小操作數(shù)問題作者：July、caopengcs、紅色標(biāo)記。致謝：fuwutu、demo。時(shí)間：二零一三年八月十二日題目詳情如下：給定一個(gè)單詞集合Diet，其中每個(gè)單詞的長(zhǎng)度都相同?，F(xiàn)從此單詞集合Diet中抽取兩個(gè)單詞A、B,我們希望通過若干次操作把單詞A變成單詞B,每次操作可以改變單詞的一個(gè)字母，同時(shí)，新產(chǎn)生的單詞必須是在給定的單詞集合Diet中。求所有行得通步數(shù)最少的修改方法。舉個(gè)例子如下：Given:A="hit"B="cog"Dict=["hot","dot","dog","lot","log"]Return[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]即把字符串A="hit"轉(zhuǎn)變成字符串B="cog"，有以下兩種可能："hit"->"hot"->"dot"->"dog"->"cog"；"hit"->"hot"->"lot"->"log"->"cog"。詳解：本題是一個(gè)典型的圖搜索算法問題。此題看似跟本系列的第29章的字符串編輯距離相似，但其實(shí)區(qū)別特別大，原因是最短編輯距離是讓某個(gè)單詞增加一個(gè)字符或減少一個(gè)字符或修改一個(gè)字符達(dá)到目標(biāo)單詞，來(lái)求變換的最少次數(shù)，但此最小操作數(shù)問題就只是改變一個(gè)字符。我們知道，在圖搜索算法中，有深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS，而題目中并

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

//copyright@caopengcs//updated@July08/12/2013classSolution{public://help函數(shù)負(fù)責(zé)找到所有的路徑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)達(dá)到終點(diǎn)了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){ //起點(diǎn)終點(diǎn)恰好相等returnanswer;}//把起點(diǎn)終點(diǎn)加入字典的mapdict.insert(start);dict.insert(end);set<string>::iteratordt;vector<string>word;map<stringint>allword;//把set轉(zhuǎn)換為map，這樣每個(gè)單詞都有編號(hào)了。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)化版的思路，讓每個(gè)單詞每個(gè)位置變更大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;}}}//以下是標(biāo)準(zhǔn)bfs過程queueint>q;vectorint>d;d.resize(n,-1);intfrom=allword[start],to=allword[end];d[to]=0;//d記錄的是路徑長(zhǎng)度，-1表示沒經(jīng)過q.push(to);vector<vectorint>>next;next.resize(n);while(!q.empty()){intx=q.front(),now=d[x]+1;//now相當(dāng)于路徑長(zhǎng)度//當(dāng)now>d[from]時(shí)，則表示所有解都找到了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é)點(diǎn)都存下來(lái)，很有可能每一步的搜到的節(jié)點(diǎn)個(gè)數(shù)越來(lái)越多,但最后的目的節(jié)點(diǎn)卻只有一個(gè)。后半段的很多搜索都是白耗時(shí)間了。上面給出了單向BFS的解法，但是實(shí)際上雙向BFS性能優(yōu)于單向BFS。舉個(gè)例子如下，第1步，是起點(diǎn)，1個(gè)節(jié)點(diǎn)，第2步，搜到2個(gè)節(jié)點(diǎn)，第3步，搜到4個(gè)節(jié)點(diǎn)，第4步搜到8個(gè)節(jié)點(diǎn)，第5步搜到16個(gè)節(jié)點(diǎn)，并且有一個(gè)是終點(diǎn)。那這里共出現(xiàn)了31個(gè)節(jié)點(diǎn)。從起點(diǎn)開始廣搜的同時(shí)也從終點(diǎn)開始廣搜，就有可能在兩頭各第3步，就相遇了，出現(xiàn)的節(jié)點(diǎn)數(shù)不超過(1+2+4)*2=14個(gè)，如此就節(jié)省了一半以上的搜索時(shí)間。下面給出雙向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