【word-ladder】

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start ="hit"

end ="cog"

dict =["hot","dot","dog","lot","log"]

As one shortest transformation is"hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

題意：将單詞一通過給定的詞典中進行轉換，傳回轉換次數最少，轉換成end單詞；

思路：使用廣度優先周遊； 1、将start放入隊列q1，初始count=0; 2、當q1非空，逐個周遊q1中的單詞，count++; 3、設q1中的單詞為str, 尋找其臨近單詞s,如果s等于end傳回count+1 否則，将s放入隊列q2中， 4、将q1和 q2 交換，繼續執行2

class Solution
{
	int ladderLength(string start, string end, unorder_set<string>& dict)
	{
		queue<string> q1, q2, *p1, *p2;

		int count = 0;
		for (p1=&q1, p2=&q2, p1->push(start); p1->size(); swap(p1, p2))
		{
			++count;
			for (string str; p1->size(); p1->pop())
			{
				str = p1->front();
				for (int i=0; i<str.length(); i++)
				{
					string s = str;
					for (char ch = 'a'; ch <= 'z'; ++ch)
					{
						if (ch==str[i])
						{
							continue;
						}
						s[i] = ch;
						if (s==end)
						{
							return count + 1;
						}

						if (dict.find(s)!=dict.end())
						{
							p2->push(s);
							dict.erase(s);
						}
					}
				}
			}
		}
		return 0;
	}
};