图论第5天

 127.单词接龙

 需要cout看一下过程。

#include <iostream>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace ::std;class Solution
{
public:int ladderLength(string beginWord, string endWord, vector<string> &wordList){unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 换成unordered_set后查询速度增加if (wordSet.find(endWord) == wordSet.end())return 0;unordered_map<string, int> visitMap; //<word，查询到的路径长度>queue<string> que;que.push(beginWord);visitMap.insert(pair<string, int>(beginWord, 1));while (!que.empty()){string cur_word = que.front();que.pop();int path = visitMap[cur_word];for (int i = 0; i < cur_word.size(); i++){string new_word = cur_word;for (int j = 0; j < 26; j++){new_word[i] = j + 'a';if (new_word == endWord)return path + 1;if (wordSet.find(new_word) != wordSet.end() && visitMap.find(new_word) == visitMap.end()){visitMap.insert(pair<string, int>(new_word, path + 1));que.push(new_word);}}cout << cur_word << endl;cout << i << endl;for (pair<string, int> x : visitMap){cout << "visitMap[" << x.first << "] = " << x.second << "   ";}cout << endl;}}return 0;}
};int main()
{Solution syz;string beginWord = "hit", endWord = "cog";vector<string> wordList;wordList.push_back("hot");wordList.push_back("dot");wordList.push_back("dog");wordList.push_back("lot");wordList.push_back("log");wordList.push_back("cog");syz.ladderLength(beginWord, endWord, wordList);return 0;
}

cout运行结果需要看一下，理解一下过程：

所有的word的字母都需要执行一次，所以是0、1、2，

hit 改 h是没有单词加入的，改i会有个hot，改t没有单词加入，所以visitMap里不变。hit这时候已经pop()。

hot改h，增加两个dot\lot，改o\t没有，hot.pop()。

竟然是先dot后lot，跟push顺有关。hot会先push “ d ” 后 push " l "

dot，d\o都没有，t改完，出现一个dog，g会继续往下走,dot.pop() 

lot，l\o都没有，出现log.pop()

这时候que里，front 是dog，然后是 log

dog直接知道cog。visitMap[dog] = 4，4 + 1 = 5

hit
0
visitMap[hit] = 1
hit
1
visitMap[hot] = 2   visitMap[hit] = 1
hit
2
visitMap[hot] = 2   visitMap[hit] = 1
hot
0
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
hot
1
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
hot
2
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
0
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
1
visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
dot
2
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
0
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
1
visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
lot
2
visitMap[log] = 4   visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1

广搜更适合这道题，会把所有可能性在起始点周边的可能性，一点点往外扩，不会造成走冤枉路。

图论看来一道题就要很刺激啊。 T _ T。明天摸鱼看能不能做两道吧。