单词接龙2
【单词接龙2】
文章图片
和上一个单词接龙不一样在，这道题返回所有的最短路径
记录搜索路径的宽搜：
1.将普通队列更换为vector，保存所有的搜索结点，在pop时不会丢弃队头元素，只是移动front指针
2.在队列结点中增加该结点的前驱结点在队列中的下标信息，可通过该下标找到是从队列中的哪个结点搜索到当前结点的
多条路径的保存：
到达某一位置可能存在多条路径，使用映射记录到达每个位置的最短需要步数，新拓展到的位置只要未曾到达或到达步数与最短步数相同，即将该位置添加到队列中，从而存储了从不同前驱到达该位置的情况
struct item{
string node;
int pre_pos;
int step;
item(string _node,int _pre_pos,int _step):node(_node),pre_pos(_pre_pos),step(_step){}
};
class Solution {
public:
bool connect(string& s1,string& s2)
{
int cnt = 0;
for(int i =0;
i& wordlist,map >& graph)
{
int has_beginword = 0;
for(int i =0;
i& graph,vector- & q,vector
& end_word_pos)
{
map visit;
//<单词，步数>
int min_step = 0;
q.push_back(item(beginword,-1,1));
//起始单词的前驱为-1
visit[beginword] = 1;
int front = 0;
//队列头指针while(front != q.size())
{
string node = q[front].node;
int step = q[front].step;
if(min_step != 0&&step > min_step)//step > min_step代表所有到终点的路径都搜索完成
break;
if(node == endword)
{
min_step = step;
//搜索到结果时，记录到达终点
end_word_pos.push_back(front);
}vector neighbors = graph[node];
for(int i =0;
i findLadders(string beginWord, string endWord, vector& wordList) {
map > graph;
vector- q;
vector
end_word_pos;
construct_graph(beginWord,wordList,graph);
BFS(beginWord,endWord,graph,q,end_word_pos);
vector res;
//保存路径结果
for(int i = 0;
i=0;
--j)
res[i].push_back(path[j]);
}return res;
}
};
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长