126. Word Ladder II

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();		}	}};