Leetcode Word Ladder II

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) 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"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Leetcode 第一难题，六星级！ 帆船酒店来了！

难点考点：

1 知道什么时候去掉重复，会使用set容器避免重复

2 高级层序遍历树应用

3 适当时候去掉字典中的单词避免重复

4 知道什么时候结束层序

5 利用高级数据结构保存结果，本程序使用unordered_map<string, vector<string> >

6 使用递归回溯法，利用高级数据结构，构造最终结果

每一点几乎都可以成为一个大题，都糅合在一起了，加上各个细节，那么就构成了一个六星级难题了。

2 下一层保存单词不能重复，否则会有很多多余的单词处理，造成time limit excessed

//2014-2-18 update
	vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict)
	{
		vector<vector<string> > rs;
		unordered_map<string, vector<string> > ump_sv;
		dict.erase(start);
		dict.erase(end);

		vector<string> qu[2];
		set<string> sst;
		qu[0].push_back(start);
		bool idx = false;
		bool finished = false;
		while (!qu[idx].empty())
		{
			while (!qu[idx].empty())
			{
				string s = qu[idx].back();
				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) 
						{
							finished = true;
							ump_sv[s].push_back(qu[idx].back());
						}
						else if (dict.count(s))
						{
							ump_sv[s].push_back(qu[idx].back());
							qu[!idx].push_back(s);
						}
					}
					s[i] = a;
				}//for
				qu[idx].pop_back();
			}//while
			if (finished) break;
			idx = !idx;

			sst.clear();
			sst.insert(qu[idx].begin(), qu[idx].end());
			qu[idx].assign(sst.begin(), sst.end());

			for (auto x:qu[idx]) dict.erase(x);
		}//while
		if (!ump_sv.count(end)) return rs;
		vector<string> tmp(1, end);
		constructLadder(rs, tmp, ump_sv, start, end);
		return rs;
	}
	void constructLadder(vector<vector<string> > &rs, vector<string> &tmp, 
		unordered_map<string, vector<string> > &ump_sv, string &start, string &cur)
	{
		if (cur == start)
		{
			rs.push_back(tmp);
			reverse(rs.back().begin(), rs.back().end());
			return;
		}
		vector<string> v = ump_sv[cur];
		for (int i = 0; i < v.size(); i++)
		{
			tmp.push_back(v[i]);
			constructLadder(rs, tmp, ump_sv, start, v[i]);
			tmp.pop_back();
		}
	}

Leetcode Word Ladder II,布布扣,bubuko.com

Leetcode Word Ladder II

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