127. Word Ladder
C++，bfs，差不多200ms。思路如下：
- 首先用unordered_set构造单词列表，因为unordered_set底层用hash实现，搜索速度比vector快得多，一个O(1)，一个O(n)；
- 用unordered_map作为记录层数的表，beginWord肯定就是第一层；
- 首先要确定endWord在列表里，不然就返回0；
- 然后就是bfs标准操作了。。。
- 比较重要的就是如何搜索邻接点：
- 对于每个当前结点，搜索下一个单词，不要一一去对比；
- 可以对当前单词cur，循环对单词里的每个字母用26个字母轮流替换，产生新单词temp，temp和cur只会相差一个字母；
- 前面建立的unordered_set底层用hash实现的，可以temp直接进行查找，是否在单词列表里；
- 如果在列表里，说明temp就是cur的邻结点，temp的层数 = cur层数 + 1；
- 最后判断temp是不是endWord，是就返回层数；
知识点：对于无权图的bfs其实就是dijkstra！
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> word_set(wordList.begin(), wordList.end());
unordered_map<string, int> word_dict;
if (word_set.find(endWord) == word_set.end()) return 0;
queue<string> q;
q.push(beginWord);
word_dict[beginWord] = 1;
while (!q.empty()) {
string cur = q.front();
q.pop();
for (int i = 0; i < cur.size(); i++) {
string temp = cur;
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch == temp[i]) continue;
temp[i] = ch;
if (word_set.find(temp) != word_set.end() && word_dict[temp] == 0) {
word_dict[temp] = word_dict[cur] + 1;
q.push(temp);
if (temp == endWord) return word_dict[temp];
}
}
}
}
return 0;
}
};
这是4000+ms的bfs版本，想了很久才知道为什么要那么久！！！
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
wordList.resize(wordList.size() + 1);
int size = wordList.size();
int s = 0, d = -1;
for (int i = size - 1; i >= 1; i--) {
wordList[i] = wordList[i-1];
if (wordList[i-1] == endWord) d = i;
}
if (d == -1) return 0;
wordList[0] = beginWord;
vector<vector<int>> g(size);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i == j) continue;
if (is_adjacent(wordList[i], wordList[j]))
g[i].push_back(j);
}
}
vector<int> level(size);
queue<int> q;
q.push(s);
level[s] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int next : g[now]) {
if (!level[next]) {
q.push(next);
level[next] = level[now] + 1;
}
if (next == d) return level[next];
}
}
return level[d];
}
bool is_adjacent(string a, string b) {
int cnt = 0;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i]) cnt++;
if (cnt > 1) return false;
}
if (cnt == 1) return true;
else return false;
}
};
