单词接龙(双向广度优先遍历BFS)

试题叙述

取值两个单字（beginWord 和 endWord）和两个词典，找寻从 beginWord 到 endWord 的极短切换字符串串的宽度。切换需遵从如下表所示准则：

1.每天切换只能改变两个拉丁字母。 2.切换过程中的尾端单字必须是词典中的单字。

表明:

1.假如不存有这种的切换字符串串，回到 0。 2.大部份单字具有完全相同的宽度。 3. 大部份单字只由小写拉丁字母组成。 4.词典中不存有多次重复的单字。 5. 你可以假定 beginWord 和 endWord 亦然空的，且两者不完全相同。

实例 1: 输入: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出: 5 表明: 两个极短切换字符串串是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 回到它的宽度 5。实例 2: 输入: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”] 输出: 0 表明: endWord “cog” 无此词典中，因而无法进行切换。

由于试题中要求的是极短切换字符串串的宽度，因而首先想到的就是深度优先选择搜寻。

根据Whether预测关键点:

从初始词开始，每天变两个拉丁字母，经过m次转换，变为完结词，期许m尽可能小。我们需要找寻接邻关系，比如说hit它变两个拉丁字母会变为_it、h_t、hi_形式的单字，接着看那个新词汇与否存有于单字表，假如存有，就找寻了两个下几层的切换词。同时，要防止多次重复出访，比如说hot->dot->hot这种瘤果，只会不免切换的宽度。因而，要将下两个切换词从单字表中删掉（单字表的单字是惟一的）。可能下几层的单字有数个，都要实地考察，哪条切换方向先碰到终点词，它就极短。

依照预测得出写作文关键步骤:

由两个结点点出下几层的接邻点，因而用BFS，把单字看做结点。保护两个堆栈，让终点词Murviel，step为1，接着奥梅利实地考察。将它的每个字符串变为26拉丁字母之一，逐一看与否在单字表，假如在，那个新词汇为下几层的变革词。将它Murviel，它的step+1，并从单字表中略去那个词。奥梅利Murviel…多次重复，当奥梅利的单字和终点词完全相同，表明碰到了终点词，回到它的step。当堆栈入空时，BFS完结，仍旧没碰到终点词，没方向通向终点，回到 0。

具体实现标识符如下表所示：

classSolution{public:intladderLength(stringbeginWord,stringendWord,vector<string>&wordList){unordered_set<string>dict(wordList.begin(),wordList.end());if(dict.find(endWord)==dict.end())return0;//初始化初始点和终点unordered_set<string>frontSet,backSet,tmp,visited;frontSet.insert(beginWord);backSet.insert(endWord);intstep=1;while(!frontSet.empty()&&!backSet.empty()){if(backSet.size()<frontSet.size()){tmp=frontSet;frontSet=backSet;backSet=tmp;}tmp.clear();for(autoword:frontSet){for(inti=0;i<word.size();++i){charold=word[i];//开始转换for(charc=a;c<=z;++c){if(old==c)continue;word[i]=c;if(backSet.find(word)!=backSet.end())return++step;if(visited.find(word)==visited.end()&&dict.find(word)!=dict.end()){tmp.insert(word);visited.insert(word);}}word[i]=old;}}frontSet=tmp;++step;}return0;}};

AC结果：

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，请发送邮件至1936152778@qq.com举报，一经查实，本站将立刻删除。
如若转载，请注明出处：https://www.caopanquan.cn/974.html

单词接龙(双向广度优先遍历BFS)

试题叙述

相关推荐