LeetCode: Word Ladder [126]

【题目】

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 length 5.

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, 一个词典，要求找出start到end的最短转换序列。

要求转换过程中每次仅仅能改变一个字符，转换的中间单词必须在词典中。

有三点说明：

1. 假设没有转换序列，则返回0

2. 起始单词以及字典中的全部单词的长度都是相等的

3. 全部单词中的单词都保证小写。

【思路】

最直接的办法是先找出start和词典中每一个单词在序列中全部合法的next（下一个）单词集合。事实上就是构造了一个邻接矩阵。然后邻接矩阵上跑BFS，计算最小的转换层次，即为本题要求的最少的转换次数。这样的的复杂度是O(n^2)，显然这么做就跪了。

我们不用傻逼呵呵的去建图。吃力不讨好。我们仅仅须要针对序列每一个位置上的词进行考察就能够了，

首先看start, start每一位分别用a~z(除了自有的字母)替换，然后从词典中找出一次转换可达的单词集合，把这些一次可达的单词从词典中删除。

然后跟start同样，我们对一次转换可达的每一个单词值的每一位分别用a~z(除了自有的字母)替换。然后从词典中找出二次可达的单词集合，把这些二次可达的单词从词典中删除。

反复上面的过程，我们能够找到3次，4次。5次...转换可达的单词。

在转换过程中推断转换后的结果是否是end。假设已经能转换成end，则直接返回当前转换次数就可以。

因为单词长度一定。如果为K，我们用a-z来替换每一位的方法来寻找后继单词，即使运气背到家没有这种转换序列。我们把左右的单词都推断了一遍，，复杂度也仅仅有O(26Kn)，比O(n^2)快非常多。

【代码】

class Solution {

public:

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

        if(start==end)return 1;

        int level=0;

        queue<string> q1;

        queue<string> q2;

        //初始化q1

        q1.push(start);

        level=1;

        while(!q1.empty()||!q2.empty()){

            level++;

            if(!q1.empty()){

                while(!q1.empty()){

                    string word=q1.front(); q1.pop();

                    //确定转换序列中的后继单词

                    for(int i=0; i<word.length(); i++){

                        string tword=word;

                        for(char c='a'; c<='z'; c++){

                            if(tword[i]!=c){

                                tword[i]=c;

                                //推断是否是end

                                if(tword==end)return level;

                                //推断后继单词是否在dict中，假设在，即合法，增加到q2中

                                if(dict.find(tword)!=dict.end()){

                                    q2.push(tword);

                                    dict.erase(tword);

                                }

                            }

                        }

                    }

                }

            }

            else{

                while(!q2.empty()){

                    string word=q2.front(); q2.pop();

                    //确定转换序列中的后继单词

                    for(int i=0; i<word.length(); i++){

                        string tword=word;

                        for(char c='a'; c<='z'; c++){

                            if(tword[i]!=c){

                                tword[i]=c;

                                //推断是否是end

                                if(tword==end)return level;

                                //推断后继单词是否在dict中。假设在。即合法。增加到q1中

                                if(dict.find(tword)!=dict.end()){

                                    q1.push(tword);

                                    dict.erase(tword);

                                }

                            }

                        }

                    }

                }

            }

        }

        return 0;

    }

};

巴特西

LeetCode: Word Ladder [126]

【题目】

【题意】

【思路】

【代码】

最新文章

热门文章