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.

給出一個開始單詞和結(jié)束單詞，以及一系列的轉(zhuǎn)換單詞，問最少幾次轉(zhuǎn)換能使開始單詞轉(zhuǎn)換成結(jié)束單詞。這里主要用到3個unordered_set<string>類型的集合，其中2個用來存放從兩端“延伸”出來的單詞（beginSet和endSet），還有一個存放剩余的單詞（wordSet）。為了減少計算時間，每次選擇元素個數(shù)比較少的集合（beginSet和endSet）進(jìn)行操作，操作的集合設(shè)為set1，另一個為set2。對set1每一個單詞的每一個字母進(jìn)行改變（每個字每改變26次），每次改變在set2中查找是否有當(dāng)前單詞，如果有的話說明兩個集合能“連通”了，就返回答案；另外還要在wordSet中查找是否有該單詞，有的話收集起來（放在set3中），本輪結(jié)束后令set1変為set3（因為原本的單詞已經(jīng)沒用了，總不能變回去啦），收集之外還要在wordSet中刪除該單詞。初始答案為2，每輪操作答案都加2。要注意的是如果wordSet中不含結(jié)束單詞是無法完成轉(zhuǎn)換的，這種情況返回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;	}};