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的升級版，要找出所有使開始單詞轉換成結束單詞的最短的轉換路徑。在上一道題的基礎上修改，比上一題增加的是，要記錄下變換的路徑，這里用unordered_map來記下每個單詞對應的下一個單詞列表。因為是從兩端開始延伸的，但變換順序是單向的，所以從尾端延伸的要以變換的單詞為鍵值，將當前單詞加入對應的下一個單詞列表。最后用深度優先搜索就能得到全部答案。
還有一點和127題的實現不一樣的是，當前單詞在wordSet中找到一個可變換單詞就收集下來并立刻從wordSet中刪除，但這里不能立刻刪除，等遍歷完當前集合全部單詞才根據set3刪除wordSet中的單詞（對127題立刻和不立刻刪除沒區別），這時考慮到這種情況：當前集合有marks和paris，wordSet中有parks，如果marks確定了能變換成parks，然后把parks從wordSet中刪除，下面paris就沒有下一個單詞了（斷鏈了。。），這樣答案就不全了，所以wordSet等遍歷完當前集合全部單詞才更新。
代碼：
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();		}	}};