Word Ladder - LeetCode
给定一个两个词 beginWord, endWord 与一个unordered_set wordList。从beginWord开始，每次更改一个字母变到wordList中包含的一个词。求最少几次可以从beginWord变到endWord
思路是从beginWord开始，查找在wordDict里面所有改变一个字母能变成的词，加到toVisit里面。然后在查找toVisit里面的词。这样一层一层的查找方法显然是BFS
当已经找到endWord时，查找已完成，返回res。PS：res初始为2(beginWord 与 endWord)
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
wordList.insert(endWord);
queue<string> toVisit;
bfs(beginWord, wordList, toVisit);
int res = 2;
while(not toVisit.empty()) {
int size = toVisit.size();
while (size--) {
auto cur = toVisit.front();
toVisit.pop();
if (cur == endWord) return res;
bfs(cur, wordList, toVisit);
}
res++;
}
return 0;
}
private:
void bfs(string word, unordered_set<string>& wordList, queue<string>& toVisit) {
wordList.erase(word);
for (int i = 0; i < word.length(); i++) {
char originalLetter = word[i];
for (int l = 0; l < 26; l++) {
word[i] = 'a' + l;
if (wordList.find(word) != wordList.end()) {
toVisit.push(word);
wordList.erase(word);
}
}
word[i] = originalLetter;
}
}
};
