图论第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;
for (int i = 0; i < cur_word.size(); i++)
{
string new_word = cur_word;
for (int j = 0; j < 26; j++)
{
new_word = 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 = 4，4 + 1 = 5
hit
0
visitMap = 1
hit
1
visitMap = 2 visitMap = 1
hit
2
visitMap = 2 visitMap = 1
hot
0
visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
hot
1
visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
hot
2
visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
dot
0
visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
dot
1
visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
dot
2
visitMap = 4 visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
lot
0
visitMap = 4 visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
lot
1
visitMap = 4 visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1
lot
2
visitMap = 4 visitMap = 4 visitMap = 3 visitMap = 3 visitMap = 2 visitMap = 1 广搜更得当这道题，会把所有大概性在起始点周边的大概性，一点点往外扩，不会造成走冤枉路。
图论看来一道题就要很刺激啊。 T _ T。明天摸鱼看能不能做两道吧。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]