解法一:BFS
1、思路
-
把
wordList
想象成一张图,两个单词若只有一个字母只差,则它们之间有一条连线; -
首先将
wordList
中的单词放入哈希表中,每当一个单词被访问过,就从哈希表删除它; -
把
beginWord
放入队列q1
中,通过getNeighbors
方法取得它所有可能的单词演变,其数量为$25N$,$N$为单词长度。遍历这些单词演变,判断它们是否存在于wordList
中,若存在,则表示它是当前单词的一个邻近单词演变; -
将所有符合条件的邻近单词演变放入
q2
中,每次交换队列q1
与q2
都意味着距离初始节点距离为d
的节点都访问完毕,接下来将访问距离为d + 1
的节点,因此距离加1。
2、代码
class Solution {
public:
void clear(queue<string>& q) //清空队列的方法
{
queue<string> empty;
swap(empty, q);
}
vector<string> getNeighbors(string word) //取得word的所有邻近单词演变
{
vector<string> neighbors;
for (int i = 0; i < word.length(); ++ i)
{
char old = word[i];
for (char ch = 'a'; ch <= 'z'; ++ ch)
{
if (old != ch)
{
word[i] = ch;
neighbors.push_back(word);
}
}
word[i] = old; //还原当前单词
}
return neighbors;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<string> q1, q2;
unordered_set<string> hash(wordList.begin(), wordList.end());
if (hash.find(endWord) == hash.end()) return 0; //不能转换的情况
int len = 1;
q1.push(beginWord);
while (!q1.empty()) //开始BFS
{
string word = q1.front();
q1.pop();
if (word == endWord) return len;
vector<string> neighbors = getNeighbors(word);
for (string neighbor : neighbors)
{
if (hash.find(neighbor) != hash.end())
{
q2.push(neighbor);
hash.erase(neighbor);
}
}
if (q1.empty()) //俩队列交换
{
++ len;
q1 = q2;
clear(q2);
}
}
return 0;
}
};
解法二:双向BFS
1、思路
-
分别从起始节点和目标节点出发不断搜索,直到在中间某个位置相遇,这种方式能使图中只有部分节点被搜索到,降低了空间复杂度;
-
一共使用三个
哈希set
,set1
和set2
分别存放两个方向上当前需要访问的节点,set3
用来存放与当前访问的节点相邻的节点; -
每次
while
循环都是从需要访问的节点数目少的方向搜索,这样做是为了缩小搜索的空间,我们确保set1
中需要访问的节点数更少; -
遍历
set1
中的节点word
,若某个与word
相邻的节点neighbor
存在于set2
中,则说明两个不同方向的搜索相遇,已经找到了一条起始节点和目标节点的最短路径。
2、代码
class Solution {
public:
vector<string> getNeighbors(string word)
{
vector<string> neighbors;
for (int i = 0; i < word.length(); ++ i)
{
char old = word[i];
for (char ch = 'a'; ch <= 'z'; ++ ch)
{
if (old != ch)
{
word[i] = ch;
neighbors.push_back(word);
}
}
word[i] = old;
}
return neighbors;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> set1, set2;
unordered_set<string> hash(wordList.begin(), wordList.end());
if (hash.find(endWord) == hash.end()) return 0;
int len = 2;
set1.insert(beginWord);
set2.insert(endWord);
hash.erase(endWord);
while (!set1.empty() && !set2.empty())
{
if (set1.size() < set2.size()) //保持set1中元素最少
{
unordered_set<string> tmp = set1;
set1 = set2;
set2 = tmp;
}
unordered_set<string> set3;
for (string word : set1)
{
vector<string> neighbors = getNeighbors(word);
for (string neighbor : neighbors)
{
if (set2.find(neighbor) != set2.end()) //已经相遇
{
return len;
}
if (hash.find(neighbor) != hash.end())
{
set3.insert(neighbor);
hash.erase(neighbor);
}
}
}
++ len; //每个循环距离加1
set1 = set3;
}
return 0;
}
};