图论第5天

 127.单词接龙
 需要cout看一下过程。

1. #include <iostream>
2. #include <queue>
3. #include <stack>
4. #include <unordered_map>
5. #include <unordered_set>
6. #include <vector>
7. using namespace ::std;
9. class Solution
10. {
11. public:
12.     int ladderLength(string beginWord, string endWord, vector<string> &wordList)
13.     {
14.         unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 换成unordered_set后查询速度增加
15.         if (wordSet.find(endWord) == wordSet.end())
16.             return 0;
17.         unordered_map<string, int> visitMap; //<word，查询到的路径长度>
18.         queue<string> que;
19.         que.push(beginWord);
20.         visitMap.insert(pair<string, int>(beginWord, 1));
21.         while (!que.empty())
22.         {
23.             string cur_word = que.front();
24.             que.pop();
25.             int path = visitMap[cur_word];
26.             for (int i = 0; i < cur_word.size(); i++)
27.             {
28.                 string new_word = cur_word;
29.                 for (int j = 0; j < 26; j++)
30.                 {
31.                     new_word[i] = j + 'a';
32.                     if (new_word == endWord)
33.                         return path + 1;
34.                     if (wordSet.find(new_word) != wordSet.end() && visitMap.find(new_word) == visitMap.end())
35.                     {
36.                         visitMap.insert(pair<string, int>(new_word, path + 1));
37.                         que.push(new_word);
38.                     }
39.                 }
40.                 cout << cur_word << endl;
41.                 cout << i << endl;
42.                 for (pair<string, int> x : visitMap)
43.                 {
44.                     cout << "visitMap[" << x.first << "] = " << x.second << "   ";
45.                 }
46.                 cout << endl;
47.             }
48.         }
49.         return 0;
50.     }
51. };
53. int main()
54. {
55.     Solution syz;
56.     string beginWord = "hit", endWord = "cog";
57.     vector<string> wordList;
58.     wordList.push_back("hot");
59.     wordList.push_back("dot");
60.     wordList.push_back("dog");
61.     wordList.push_back("lot");
62.     wordList.push_back("log");
63.     wordList.push_back("cog");
64.     syz.ladderLength(beginWord, endWord, wordList);
65.     return 0;
66. }

复制代码

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

1. hit
2. 0
3. visitMap[hit] = 1
4. hit
5. 1
6. visitMap[hot] = 2   visitMap[hit] = 1
7. hit
8. 2
9. visitMap[hot] = 2   visitMap[hit] = 1
10. hot
11. 0
12. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
13. hot
14. 1
15. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
16. hot
17. 2
18. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
19. dot
20. 0
21. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
22. dot
23. 1
24. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
25. dot
26. 2
27. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
28. lot
29. 0
30. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
31. lot
32. 1
33. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
34. lot
35. 2
36. visitMap[log] = 4   visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1

复制代码

广搜更得当这道题，会把所有大概性在起始点周边的大概性，一点点往外扩，不会造成走冤枉路。
图论看来一道题就要很刺激啊。 T _ T。明天摸鱼看能不能做两道吧。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。