解题思路
-
一个重要的能力就是将具体的问题抽象为已知的知识结构中。这道题需要仔细思考,其实就是一道 BFS 问题。
-
明白了是 BFS,具体代码上也会产生巨大的性能差异,下面列出我一开始写的性能较差的版本和性能很好的版本。
代码
// Slow Solution
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string, bool> wordMap;
unordered_set<string> wordSet(wordList.begin(), wordList.end());
for (auto word : wordList) {
wordMap[word] = (word==beginWord)? false: true;
}
vector<string> bfs;
bfs.push_back(beginWord);
int res = 1;
while (!bfs.empty()) {
res++;
vector<string> temp;
for (auto word : bfs) {
for (auto it = wordMap.begin(); it != wordMap.end(); ++it) {
if (it->second == true && isNext(word, it->first)) {
if (it->first == endWord) {
return res;
}
temp.push_back(it->first);
it->second = false;
}
}
}
swap(bfs, temp);
}
return 0;
}
bool isNext(const string& word1, const string& word2) {
int distance = 0;
for (int i = 0; i < word1.size(); ++i) {
if (word1[i] != word2[i] && ++distance > 1) {
return false;
}
}
return (distance == 1) ? true: false;
}
};
// Fast Solution
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> start{beginWord};
unordered_set<string> end{endWord};
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) {
return 0;
}
int step = 1;
while (!start.empty() && !end.empty()) {
step++;
unordered_set<string> temp;
if (start.size() > end.size()) {
swap(start, end);
}
for (auto w : start) {
for (int i = 0; i < w.size(); ++i) {
string word = w;
for (char c = 'a'; c <= 'z'; ++c) {
if (c == word[i]) {
continue;
} else {
word[i] = c;
}
if (end.count(word)) {
return step;
}
if (wordSet.count(word)) {
temp.insert(word);
wordSet.erase(word);
}
}
}
}
swap(start, temp);
}
return 0;
}
};