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:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
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.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Example 2:
Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore no possibletransformation.
很有意思的一个题。给定两个单词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。
二刷。设置一个visited数组也许是更常规的做法：
class Solution {
public:
bool IsConnect(const string &a, const string &b) {
int diff = 0, n = a.size();
for (int i = 0; i < n; ++i) {
if (a[i] != b[i]) {
++diff;
if (diff > 1)return false;
}
}
return diff == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = wordList.size();
if (n == 0)return 0;
vector<int> visited(n, 0);
queue<string> q;
q.push(beginWord);
int ans = 0;
while (!q.empty()) {
++ans;
int m = q.size();
for (int i = 0; i < m; ++i) {
string cur = q.front();
if (cur == endWord)return ans;
q.pop();
for (int j = 0; j < n; ++j) {
if (visited[j] == 0 && IsConnect(cur, wordList[j])) {
visited[j] = 1;
q.push(wordList[j]);
}
}
}
}
return 0;
}
};本代码提交AC，用时532MS。