[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.

题意：从一个词变为另一个词，每次只能变化一个字符，变化的中间词都在字典中，求最短的路径。

思路：图论中单源最短路，求单源最短路比较通用算法是BFS和Dijkstra，其区别在于BFS不能用于带权重图，而Dijkstra可以。另外，BFS和Dijkstra的区别是前者的时间复杂度是O(n)，后者最多优化到O(mlogn)，如果条件成立一般选择BFS。本题中，两字符串之间是无权重的，连通是1，不连通是无穷，故本题采用BFS方法。

首先，要进行图的映射，顶点是每个字符串，若是两个字符串相差1个字符且后者在dict中，就相连构成边；然后，将起点加入到队列中，遍历和其相差为1的字符串，将其加入到队列中，直到找到目标字符串（找不到就返回0）。这里值得注意的是：寻找和某一个字符相差1的字符串的方式，不是遍历字典中的每一个字符串，这样当字典中元素较多时，将会耗时严重。这次采用，对该字符串的每个位置上的字符，用26个字母进行替换，找到和其相差为1的所有字符串；还有一点值得注意的是，每次在字典中找到某一个字符串以后，要在字典中删除该字符串，这样可以避免重复查找（详细说明见这里）。以题中的例子为例，见下图：

如上图，每一层依次加入到队列中，只要先找到目标词语，就返回此时的值就行。参考了这里，代码如下：

 class Solution {

 public:

     int ladderLength(string start, string end, unordered_set<string> &dict)

     {

         queue<pair<string,int>> que;

         que.push(make_pair(start,));

         dict.erase(dict.find(start));

         while( !que.empty())

         {

             auto val=que.front();

             que.pop();

             if(val.first==end)  return val.second;

             for(int i=;i<val.first.size();++i)

             {

                 string str=val.first;

                 for(int j=;j<;++j)

                 {

                     str[i]='a'+j;

                     if(dict.find(str) !=dict.end())

                     {

                         que.push(make_pair(str,val.second+));

                         dict.erase(str);

                     }

                 }

             }

         }

         return ;

     }

 };

思路是一样的，换一种写法;

 class Solution {

 public:

     int ladderLength(string start, string end, unordered_set<string> &dict)

     {

         unordered_map<string,int> m;

         queue<string> que;

         m[start]=;

         que.push(start);

         while( !que.empty())

         {

             string val=que.front();

             que.pop();

             for(int i=;i<val.size();++i)

             {

                 string str=val;

                 for(int j=;j<;++j)

                 {

                     str[i]='a'+j;

                     if(dict.count(str)&&str==end)

                         return m[val]+;

                     if(dict.count(str)&& !m.count(str))

                     {

                         que.push(str);

                         m[str]=m[val]+;

                     }

                 }

             }

         }

         return ;

     }

 };

巴特西

[Leetcode] word ladder 单词阶梯

最新文章

热门文章