leetcode之word-ladder

题目

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example,

Given: start =“hit” end =“cog” dict =[“hot”,“dot”,“dog”,“lot”,“log”]

As one shortest transformation is"hit" -> “hot” -> “dot” -> “dog” -> “cog”, return its length5.

Note:

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

题意

如题，给定一个start和一个end 两个字符串，同时又给出一个dict字典，内部含有若干个不重复的字符串； 例如： start =“hit” end =“cog” dict =[“hot”,“dot”,“dog”,“lot”,“log”] 现在可以获知一条最短的字符串转化路径：“hit” -> “hot” -> “dot” -> “dog” -> “cog” 其长度为5:，因此返回长度5； 值得注意的是： 1、如果没有这样的一条转化路径，则直接返回0； 2、没次字符串转化，只能变动一个字符，不可同时变动多个字符； 3、所有的字符串都只包含小写字符，不用考虑大小写的问题；

解题思路

这里解题思路要清晰，类似于BFS，不停的去找下一次相邻节点群中是否有节点等于end，如果有，则返回BFS的深度； 1、先将dict中的start去掉，将end加入dict中去； 2、创建一个存放相邻节点的队列q； 3、将start加入队列中； 4、针对每次获取相邻节点，就将需要返回的length+1； 5、针对没次获取到的相邻节点，其实是有多个，所以需要循环去检索这些相邻节点到底在dict中存不存在； 6、如果存在就将该字符串加入q中，同时也加入一个数组中，这个数组记录dict中已经访问过的字符串； 7、最后将所有记录下呗访问过的字符串全部从dict中删除； 8、重复4-7；

C++实现代码

class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { dict.insert(end); //在词典里面插入end dict.erase(start); //将词典里面的start去掉 queue<string> q; //创建一个存放中间产物字符串的数组 q.push(start); //一开始先把start放进去 int length =0; while(q.size()>0){ //循环的条件是q中一定还要有中间字符串 length++; //没次循环都增加一次length int queueLength=q.size(); for(int i=0;i<queueLength;i++){ //因为每次循环时候，可能dict里面会有多个满足条件的中间字符串，这里+循环 start=q.front(); //先取出最先放进去的那个 q.pop(); //然后出个队列 if(start==end) //如果这个时候中间字符串直接等于end，则直接返回length return length; vector<string> deleteList; //创建一个vector数组，用于存放要dict中已经访问的字符串，待会儿要都删除的 for(unordered_set<string>::iterator iter=dict.begin();iter!=dict.end();iter++){ //遍历这个dict int dis=distance(start,*iter); //找到中间相邻字符串 if(dis ==1){ q.push(*iter); //如果是相邻字符串就加入到q中 deleteList.push_back(*iter); //同时记录下来dict中这个可以找到，并且已经访问过了，待会儿都删掉 } } for(int i=0;i<deleteList.size();i++){ dict.erase(deleteList[i]); //将dict中整个已经可以访问过得元素的全部都删掉~ } } } return 0; } int distance(string s1,string s2){ int count=0; for(int i=0;i<s1.size();i++){ if(s1[i]!=s2[i]) count++; } return count; } };