LeetCode Word Ladder

LeetCode Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

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.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


很有意思的一个题。给定两个单词beginWord和endWord,以及一个字典数组,问从beginWord到endWord,最少需要多少次变换,每次只能变换一个字母,而且变换的单词都必须存在于字典数组中。

很明显是一个BFS题,从beginWord开始广搜,直到第一次搜到endWord时停止,此时走过的变换数就是最小变换数。因为广搜会搜索所有的空间,那么第一次到达endWord也就是最早到达的。

当然BFS的题也都能用DFS来做,但是DFS显然会慢,想想便知,DFS必须搜索完一条完整的路径才能知道结果,才能进入下一条路径开始搜索;而BFS是每条路径同步进行,只要有一条路径到达,就结束搜索。

常规的BFS代码如下:

typedef struct Item {
	string cur;
	string used;
	int step;
	Item(string c, string u, int s) :cur(c), used(u), step(s) {};
};

class Solution {
public:
	bool differOne(const string &s1, const string &s2) {
		int cnt = 0;
		for (size_t i = 0; i < s1.size(); ++i) {
			if (s1[i] != s2[i]) {
				++cnt;
				if (cnt > 1)return false;
			}
		}
		return cnt == 1;
	}
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		size_t n = wordList.size();
		queue<Item> q;
		Item it(beginWord, string(n, '0'), 1);
		q.push(it);
		while (!q.empty()) {
			Item t = q.front();
			q.pop();
			if (t.cur == endWord)return t.step;
			for (size_t i = 0; i < n; ++i) {
				if (t.used[i] == '0'&&differOne(t.cur, wordList[i])) {
					string newUsed = t.used;
					newUsed[i] = '1';
					Item tmp(wordList[i], newUsed, t.step + 1);
					q.push(tmp);
				}
			}
		}
		return 0;
	}
};

本代码很好理解,定义一个结构体Item,cur为当前到达的单词,用一个和wordList大小相同的字符串used表示走到cur时走过的单词,step表示当前走过的步数。很可惜,这个版本的代码提交MLE,超空间了。肯定是因为Item这个结构体太大了,两个string,一个int。

后来想到一个优化的方法,当某条路径path1走到单词cur时,其他路径就没必要再经过cur了,因为一旦经过cur,必定后续步骤和path1后续要走的路径就相同了,造成了重复搜索。所以我们走过每个单词时,可以直接将该单词置空,这样后续就不会再走该路了,同时这样也不需要Item结构体了。新版代码如下:

class Solution {
public:
	bool differOne(const string &s1, const string &s2) {
		int cnt = 0;
		for (size_t i = 0; i < s1.size(); ++i) {
			if (s1[i] != s2[i]) {
				++cnt;
				if (cnt > 1)return false;
			}
		}
		return cnt == 1;
	}
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		size_t n = wordList.size();
		queue<string> q;
		q.push(beginWord);
		int step = 1;
		while (!q.empty()) {
			size_t len = q.size();
			for (size_t i = 0; i < len; ++i) {
				string t = q.front();
				q.pop();
				if (t == endWord)return step;
				for (size_t j = 0; j < wordList.size(); ++j) {
					if (wordList[j] != ""&&differOne(t, wordList[j])) {
						q.push(wordList[j]);
						wordList[j] = "";
					}
				}
			}
			++step;
		}
		return 0;
	}
};

本代码提交AC,用时632MS。

Leave a Reply

Your email address will not be published. Required fields are marked *