Given two Words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWord to endWord, such that:

For example,

Given:beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log","cog"]

Return

  [    ["hit","hot","dot","dog","cog"],    ["hit","hot","lot","log","cog"]  ]
Note:
Return an empty list if there is no such transformation sequence.All words have the same length.All words contain only lowercase alphabetic characters.You may assume no duplicates in the word list.You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
Subscribe to see which companies asked this question.
這道題是127.World Ladder的升級(jí)版，要找出所有使開(kāi)始單詞轉(zhuǎn)換成結(jié)束單詞的最短的轉(zhuǎn)換路徑。在上一道題的基礎(chǔ)上修改，比上一題增加的是，要記錄下變換的路徑，這里用unordered_map來(lái)記下每個(gè)單詞對(duì)應(yīng)的下一個(gè)單詞列表。因?yàn)槭菑膬啥碎_(kāi)始延伸的，但變換順序是單向的，所以從尾端延伸的要以變換的單詞為鍵值，將當(dāng)前單詞加入對(duì)應(yīng)的下一個(gè)單詞列表。最后用深度優(yōu)先搜索就能得到全部答案。
還有一點(diǎn)和127題的實(shí)現(xiàn)不一樣的是，當(dāng)前單詞在wordSet中找到一個(gè)可變換單詞就收集下來(lái)并立刻從wordSet中刪除，但這里不能立刻刪除，等遍歷完當(dāng)前集合全部單詞才根據(jù)set3刪除wordSet中的單詞（對(duì)127題立刻和不立刻刪除沒(méi)區(qū)別），這時(shí)考慮到這種情況：當(dāng)前集合有marks和paris，wordSet中有parks，如果marks確定了能變換成parks，然后把parks從wordSet中刪除，下面paris就沒(méi)有下一個(gè)單詞了（斷鏈了。。），這樣答案就不全了，所以wordSet等遍歷完當(dāng)前集合全部單詞才更新。
代碼：
class Solution{public:	using strset = unordered_set<string>;	using strmap = unordered_map<string, vector<string> >;	vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) 	{		strset beginSet, endSet, wordSet(wordList.begin(), wordList.end());		vector<vector<string> > res;		if(wordSet.find(endWord) == wordSet.end()) return res;		beginSet.insert(beginWord);		endSet.insert(endWord);		wordSet.erase(beginWord);		wordSet.erase(endWord);		bool isfinish = false;		while(!beginSet.empty() && !endSet.empty())		{			if(isfinish) break;			strset *set1, *set2, set3;			int choose = 1;			if(beginSet.size() <= endSet.size()) { set1 = &beginSet; set2 = &endSet; }			else { choose = 2; set2 = &beginSet; set1 = &endSet; }			for(auto iter = set1->begin(); iter != set1->end(); ++iter)			{				string cur = *iter, dup = cur;				for(int i = 0; i < cur.size(); ++i)				{					char tmp = cur[i];					for(int j = 0; j < 26; ++j)					{						cur[i] = 'a' + j; 						if(set2->find(cur) != set2->end()) 						{							isfinish = true;							if(choose == 1) strMap[dup].push_back(cur);							else strMap[cur].push_back(dup);							continue;						}						if(wordSet.find(cur) != wordSet.end())						{							set3.insert(cur);							if(choose == 1) strMap[dup].push_back(cur);							else strMap[cur].push_back(dup);						}					}					cur[i] = tmp;				}			}			for(auto it = set3.begin(); it != set3.end(); ++it) wordSet.erase(*it);			swap(*set1, set3);		}		vector<string> tmp(1, beginWord);		dfs(beginWord, endWord, tmp, res);		return res;	}PRivate:	strmap strMap;	void dfs(const string& cur, const string& endWord, vector<string>& tmp, vector<vector<string> >& res)	{		if(cur == endWord)		{			res.push_back(tmp);			return;		}		for(auto iter = strMap[cur].begin(); iter != strMap[cur].end(); ++iter)		{			tmp.push_back(*iter);			dfs(*iter, endWord, tmp, res);			tmp.pop_back();		}	}};