Leetcode 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 length 5.

Note:

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

难点考点：

1 高级树的层序遍历应用

2 hash容器unordered_set应用

3 如何构造一颗庞大枝叶的树解决问题

注意问题：

1 如何计算并保存结果

2 什么时候返回结果

3 什么时候进入下一层，什么时候结束层序遍历

4 每一层如何构造

int ladderLength(string start, string end, unordered_set<string> &dict) 
	{
		if (start == end) return 1;
		int n = start.size();
		if (n<1 || n != end.size()) return 0;

		queue<string> qs1;
		qs1.push(start);
		dict.erase(start);
		queue<string> qs2;
		int minLen = 2;

		while (!qs1.empty())
		{
			while (!qs1.empty())
			{
				string s = qs1.front();
				qs1.pop();
				for (int i = 0; i < n; i++)
				{
					//注意：要很小心，位置不能错了，每一次t都需要重置回s
					char oriChar = s[i];
					for (char a = ‘a‘; a <= ‘z‘; a++)
					{
						if (a == oriChar) continue;
						s[i] = a;
						if (s == end) return minLen;

						if (dict.find(s)!=dict.end())
						{
							qs2.push(s);
							dict.erase(s);
						}
					}
					s[i] = oriChar;
				}
			}
			qs2.swap(qs1);
			++minLen;
		}
		return 0;
	}

//2014-2-18_2 update
	int ladderLength(string start, string end, unordered_set<string> &dict) 
	{
		int ans = 1;
		dict.erase(start);
		dict.erase(end);
	
		queue<string> qu[2];
		qu[0].push(start);
		bool idx = false;
		while (!qu[idx].empty())
		{
			ans++;
			while (!qu[idx].empty())
			{
				string s = qu[idx].front();
				qu[idx].pop();

				for (int i = 0; i < s.length(); i++)
				{
					char a = s[i];
					for (char az = ‘a‘; az <= ‘z‘; az++)
					{
						s[i] = az;
						if (s == end) return ans;
						if (dict.count(s))
						{
							dict.erase(s);
							qu[!idx].push(s);
						}
					}
					s[i] = a;
				}//for
			}//while
			idx = !idx;
		}//while
		return 0;
	}

Leetcode Word Ladder

原文：http://blog.csdn.net/kenden23/article/details/19398785