[Leetcode]Word Ladder II

題目：

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

   For example,

   Given:
   start = "hit"
   end = "cog"
   dict = ["hot","dot","dog","lot","log"]

   Return

     [
       ["hit","hot","dot","dog","cog"],
       ["hit","hot","lot","log","cog"]
     ]
   

    

   Note:

   • All words have the same length.
   • All words contain only lowercase alphabetic characters.
     

     解題思路：

     這道題居然被網友標注為難度1，而另一道Word Ladder被標注為難度3。事實上在做的過程中我感覺Word Ladder II的難度比Word Ladder要高。解題的關鍵在於選取適當的數據結構，題目要求輸出所有路徑，不像Word Ladder裡一樣只需要輸出最少路徑節點數。因此不是在該層找到第一個可達節點就能返回，而是要訪問所有可達節點，並且記錄下節點之間的關系。一個節點可能經過多個下一層節點到達目的節點，也就是說一個節點可能對應多個下一層節點，同時，可能有多個節點經過字符變換以後到達下一層的某一個節點，因此一個節點可能與多個上一層節點相對應起來。因此考慮采用multimap來建立節點之間的關系。從起點開始采用BFS搜索，路徑上會經過許多無效路徑（不是最短路徑的路徑或不可達路徑），因此如果當前節點與下一層節點的關系，就會有許多干擾關系的存在。注意到與目的節點關聯的節點總是有效節點，因此在建立節點關系時，采用將當前節點與上一層節點關聯的方法，這樣一來我們最後就可以從終點出發，倒推出各條有效最短路徑。multimap的鍵為當前節點，值為與當前節點關聯的上一層節點。

     另一方面，由於采用BFS，可以采用隊列來存儲待訪問的節點。然而，在訪問節點時需要保證訪問的節點不在當前層次和上一層次的已有節點中（前者會導致重復訪問，後者會導致反復循環），需要對節點進行剪枝。對於前一個問題，可以設置一個visited標志，如果已經訪問過，就不將該節點繼續壓入待訪問隊列。對於後一個問題，可以設一個變量來記錄當前的層次數，當訪問到下一個層次時，將上一層次的所有節點從字典裡面清空。

     通過以上的步驟和細節處理，就可以建立起從目的節點到初始節點的一副有向無環圖。這時只需要用DFS算法將各條路徑記錄下來即可，需要注意到從目的節點開始DFS所得到的結果是反向的路徑，對於vector容器，可以用reverse函數將其反轉。下面給出代碼。

      

     代碼：

      

     class Solution {
     public:
         vector> findLadders(string start, string end, unordered_set &dict) {
     		vector> Path;
     		vector CurrPath;
     		unordered_set visited;
     		queue> CurrCandidate;
     		multimap father;
     		bool finded=false;
     		int curr_step=0;
     		int WordSize=start.size();
     		if(start.empty()||end.empty())return Path;
     		if(start==end){
     			CurrPath.push_back(start);
     			Path.push_back(CurrPath);
     		}
     		if(dict.count(start))dict.erase(start);
     		if(dict.count(end))dict.erase(end);
     		CurrCandidate.push(make_pair(start,1));
     		visited.insert(start);
     		while(!CurrCandidate.empty()){
     			pair CurrWord(CurrCandidate.front());
     			CurrCandidate.pop();
     			if(curr_step::iterator iter;
     				for(iter=visited.begin();iter!=visited.end();iter++){
     					dict.erase(*iter);
     				}
     				curr_step=CurrWord.second;
     				visited.clear();
     			}
     			for(int i=0;i father,string start,string end,vector &CurrPath,vector> &Path){
     		CurrPath.push_back(end);
     		if(start==end){
     			Path.push_back(CurrPath);
     			reverse(Path.back().begin(),Path.back().end());
     			CurrPath.pop_back();
     			return;
     		}
     		pair::iterator,multimap::iterator> pos=father.equal_range(end);
     		while(pos.first!=pos.second){
     			build_path(father,start,pos.first->second,CurrPath,Path);
     			pos.first++;
     		}
     		CurrPath.pop_back();
     	}
     };