leetcode：单词接龙[图广搜][无权图找最短路径]

学习要点

1. 无权图找最短路径
2. 图广搜技法

题目链接

        LCR 108. 单词接龙 - 力扣（LeetCode）

题目描述

解法：无权图找最短路径

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {// 无权图找最短路径unordered_set<string> pre_set;unordered_map<string,int> short_map;queue<string> que_str;que_str.push(beginWord);// pre_set.insert(beginWord);short_map[beginWord] = 1;for(auto& i: wordList){pre_set.insert(i);}if(pre_set.find(endWord) == pre_set.end()){return 0;}while(!que_str.empty()){string word = que_str.front(); que_str.pop();// cout << "word" << ':' << ' ' << word << endl;// string newword = word;for(int i = 0 ; i<word.size();i++){cout << endl;string newword = word;// cout << newword << endl;for(char ch = 'a'; ch<='z';ch++){newword[i] = ch;// cout << newword << endl;if(newword == endWord){return short_map[word] + 1;}if(newword != word && pre_set.find(newword) != pre_set.end() && short_map.find(newword) == short_map.end()){short_map[newword] = short_map[word] + 1;que_str.push(newword);}}}}return 0;}
};