[LeetCode]Word Ladder

这一题本质上是bfs的问题，我们要考虑的部分就是找响相邻节点的问题，我们对于每一位从a变到来看是不是在dict里，在的话就是相邻的节点，其他部分和bfs是一样的，我们记录一下扫到哪里碰到目标节点就行了，代码如下：

	public class Solution {
	public int ladderLength(String start, String end, Set<String> dict) {
	if (start == null || end == null || end == null)
	return 0;
	LinkedList<String> queue = new LinkedList<String>();
	HashSet<String> visited = new HashSet<String>();
	queue.add(start);
	visited.add(start);
	int count = 1;
	while (!queue.isEmpty()) {
	int size = queue.size();
	for (int i = 0; i < size; i++) {
	String curr = queue.removeFirst();
	if (curr.equals(end))
	return count;
	ArrayList<String> neighbors = adj(curr, dict);
	for (int j = 0; j < neighbors.size(); j++) {
	String temp = neighbors.get(j);
	if (!visited.contains(temp)) {
	visited.add(temp);
	queue.add(temp);
	}
	}
	}
	count++;
	}
	return 0;
	}
	public ArrayList<String> adj(String s, Set<String> dict) {
	ArrayList<String> res = new ArrayList<String>();
	char[] chars = s.toCharArray();
	int len = chars.length;
	for (int i = 0; i < len; i++) {
	char copy = chars[i];
	for (int j = 0; j < 26; j++) {
	char replace = (char)('a' + j);
	if (replace == copy)
	continue;
	chars[i] = replace;
	String temp = new String(chars);
	if (dict.contains(temp))
	res.add(temp);
	}
	chars[i] = copy;
	}
	return res;
	}
	}

view raw word ladder v-1.java hosted with ❤ by GitHub

另外这一题如果要优化的话，可以考虑双向bfs，时间和空间都可以优化到O(b^(d / 2))，b是branch factor，d是起点和目标的距离。我们就在起点和终点一起开始bfs就行，起点一圈，终点一圈，直到

• 起点bfs访问到了到了终点bfs访问过的节点（终点的visited set）
• 终点bfs访问到了到了起点bfs访问过的节点（起点的visited set）
• 终点或者起点的queue为空（注意如果两个node真的是联通的，那么在check到相交的部分之前不会为空）

优化的部分就考虑可以先继续搜queue size较小的那边，这样可以更节省空间，时间上也会一定程度优化，不过这只是有限的优化，不会影响时间复杂度，代码如下：

	class Solution {
	public:
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
	//bidirectional BFS
	queue<string> q1, q2;
	unordered_set<string> visited1, visited2;
	unordered_set<string> words;
	for (auto& word : wordList)words.insert(word);
	if(words.find(endWord) == words.end())return 0;
	q1.push(beginWord);
	q2.push(endWord);
	int layer1 = 0, layer2 = 0;
	while (q1.size() && q2.size())
	{
	int len1 = q1.size(), len2 = q2.size();
	++layer1;
	for (int i = 0; i < len1; ++i)
	{
	auto curr = q1.front();
	q1.pop();
	if (visited1.find(curr) != visited1.end())continue;
	if (visited2.find(curr) != visited2.end())return layer1 + layer2 - 1;
	visited1.insert(curr);
	for (auto& next : adj(curr, words))
	q1.push(next);
	}
	++layer2;
	for (int i = 0; i < len2; ++i)
	{
	auto curr = q2.front();
	q2.pop();
	if (visited2.find(curr) != visited2.end())continue;
	if (visited1.find(curr) != visited1.end())return layer1 + layer2 - 1;
	visited2.insert(curr);
	for (auto& next : adj(curr, words))
	q2.push(next);
	}
	}
	return 0;
	}
	private:
	vector<string> adj(string word, unordered_set<string>& list)
	{
	vector<string> res;
	for (int i = 0; i < word.size(); ++i)
	{
	string tmp = word;
	for (int j = 0; j < 26; ++j)
	{
	char c = 'a' + j;
	if (c == word[i])continue;
	tmp[i] = c;
	if (list.find(tmp) != list.end())
	res.push_back(tmp);
	}
	}
	return res;
	}
	};

view raw Word Ladder_bi_dir_bfs.cpp hosted with ❤ by GitHub