127. Word Ladder

Given two Words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWord toendWord, such that:

For example,

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

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",return its length 5.

Note:

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.

给出一个开始单词和结束单词，以及一系列的转换单词，问最少几次转换能使开始单词转换成结束单词。这里主要用到3个unordered_set<string>类型的集合，其中2个用来存放从两端“延伸”出来的单词（beginSet和endSet），还有一个存放剩余的单词（wordSet）。为了减少计算时间，每次选择元素个数比较少的集合（beginSet和endSet）进行操作，操作的集合设为set1，另一个为set2。对set1每一个单词的每一个字母进行改变（每个字每改变26次），每次改变在set2中查找是否有当前单词，如果有的话说明两个集合能“连通”了，就返回答案；另外还要在wordSet中查找是否有该单词，有的话收集起来（放在set3中），本轮结束后令set1変为set3（因为原本的单词已经没用了，总不能变回去啦），收集之外还要在wordSet中删除该单词。初始答案为2，每轮操作答案都加2。要注意的是如果wordSet中不含结束单词是无法完成转换的，这种情况返回0.

代码：

class Solution{public:	int ladderLength(string beginWord, string endWord, vector<string>& wordList) 	{		using strset = unordered_set<string>;		strset beginSet, endSet, wordSet(wordList.begin(), wordList.end());		if(wordSet.find(endWord) == wordSet.end()) return 0;		beginSet.insert(beginWord);		endSet.insert(endWord);		wordSet.erase(endWord);		int res = 2;		while(!beginSet.empty() && !endSet.empty())		{			strset *set1, *set2, set3;			if(beginSet.size() <= endSet.size()) { set1 = &beginSet; set2 = &endSet; }			else { set2 = &beginSet; set1 = &endSet; }			for(auto iter = set1->begin(); iter != set1->end(); ++iter)			{				string cur = *iter;				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()) return res;						if(wordSet.find(cur) != wordSet.end())						{							set3.insert(cur);							wordSet.erase(cur);						}					}					cur[i] = tmp;				}			}			swap(*set1, set3);			++res;		}		return 0;	}};