127. Word Ladder
这道题使用bfs来解决，每次将满足要求的变换单词加入队列中。
wordSet用来记录当前词典中的单词，做一个单词变换生成一个新单词，都需要判断这个单词是否在词典中，不在词典中就不能加入队列。
pathCnt用来记录遍历到的某一个词使用的次数，做一个单词变换生成一个新单词，都需要判断这个单词是否在pathCnt中，如果在，则说明之前已经达到过，这次不用再计算了，因为这次计算的path肯定比之前多。pathCnt相当于剪枝。
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set wordSet(wordList.begin(),wordList.end());
if(!wordSet.count(endWord))
return ;
unordered_map<string,int> pathCnt;
queue<string> q;
q.push(beginWord);
pathCnt[beginWord] = ;
while(!q.empty()){
string word = q.front();
q.pop();
for(int i = ;i < word.size();i++){
string newWord = word;
for(char j = 'a';j <= 'z';j++){
newWord[i] = j;
if(newWord == endWord)
return pathCnt[word] + ;
if(wordSet.count(newWord) && !pathCnt.count(newWord)){
q.push(newWord);
pathCnt[newWord] = pathCnt[word] + ;
}
}
}
}
return ;
}
};126. Word Ladder II
https://www.cnblogs.com/grandyang/p/4548184.html
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
vector<vector<string>> res;
unordered_set<string> dict(wordList.begin(), wordList.end());
vector<string> p{beginWord};
queue<vector<string>> paths;
paths.push(p);
int level = , minLevel = INT_MAX;
unordered_set<string> words;
while (!paths.empty()) {
auto t = paths.front(); paths.pop();
if (t.size() > level) {
for (string w : words) dict.erase(w);
words.clear();
level = t.size();
if (level > minLevel) break;
}
string last = t.back();
for (int i = ; i < last.size(); ++i) {
string newLast = last;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newLast[i] = ch;
if (!dict.count(newLast)) continue;
words.insert(newLast);
vector<string> nextPath = t;
nextPath.push_back(newLast);
if (newLast == endWord) {
res.push_back(nextPath);
minLevel = level;
} else paths.push(nextPath);
}
}
}
return res;
}
};