【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;
	}
};