LeetCode 127. Word Ladder 单词接龙(C++/Java)

时间:2020-02-17 silentteller 人气:4

题目：

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWordis not a transformed word.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

分析：

给定起始和终止两个单词，和一个单词列表，要求我们使用列表中的单词将起始和终止单词连接起来，连接的规则是要求每次只改变一个字符，且在列表中存在，终止单词也需要在列表中。

我们可以利用广度优先搜索，从起始单词开始，将每一位字符从a到z依次改变，如果改变后的单词在列表中，就记录下来，并在集合中删去，这样做的目的是为了防止重复的搜索，例如dog-dop-dog，这样是浪费时间的，当新加入的单词和最终单词相同时，返回步骤数即可，如果保存搜索单词的集合(队列)为空时，证明已经搜索结束，且没有找到，返回0即可。

还可以利用双向广度优先搜索进行优化，思想就是同时从起始单词和终止单词开始搜索，也是通过改变字符，且在单词列表中便加入到两个搜索集中，当一侧搜索出来的单词，在另一侧的搜索单词集中，意味着出现了解。至于搜索的次序，如果当一方的集合中的单词数量小于另一方时，就优先从数量小的集合开始搜索。

程序：

C++

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //set<string> dict;
        unordered_set<string> dict;
        for(string s:wordList)
            dict.insert(s);
        if(dict.count(endWord) == 0)
            return 0;
        queue<string> q;
        q.push(beginWord);
        int l = beginWord.length();
        int step = 0;
        while(!q.empty()){
            step++;
            int len = q.size();
            for(int i = 0; i < len; ++i){
                string word = q.front();
                q.pop();
                for(int j = 0; j < l; ++j){
                    char ch = word[j];
                    for(int k = 'a'; k <= 'z'; ++k){
                        if(k == ch)
                            continue;
                        word[j] = k;
                        if(word == endWord)
                            return step+1;
                        if(dict.count(word) == 0)
                            continue;
                        q.push(word);
                        dict.erase(word);
                    }
                    word[j] = ch;
                }
            }
        }
        return 0;
    }
};

//Bidirectional BFS
//Runtime: 28 ms, faster than 98.16% of C++ online submissions for Word Ladder.
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //set<string> dict;
        unordered_set<string> dict;
        for(string s:wordList)
            dict.insert(s);
        if(dict.count(endWord) == 0)
            return 0;
        unordered_set<string> q1;
        unordered_set<string> q2;
        q1.insert(beginWord);
        q2.insert(endWord);
        int l = beginWord.length();
        int step = 0;
        while(!q1.empty() && !q2.empty()){
            step++;
            if(q1.size() > q2.size())
                swap(q1, q2); 
            unordered_set<string> q;
            for(string word:q1){
                for(int j = 0; j < l; ++j){
                    char ch = word[j];
                    for(int k = 'a'; k <= 'z'; ++k){
                        if(k == ch)
                            continue;
                        word[j] = k;
                        if(q2.count(word))
                            return step+1;
                        if(dict.count(word) == 0)
                            continue;
                        q.insert(word);
                        dict.erase(word);
                    }
                    word[j] = ch;
                }
            }
            swap(q, q1);
        }
        return 0;
    }
};

Java

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if(!dict.contains(endWord))
            return 0;
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        int l = beginWord.length();
        int step = 0;
        while(!q.isEmpty()){
            step++;
            int len = q.size();
            for(int i = 0; i < len; ++i){
                //String word = q.poll();
                StringBuilder word = new StringBuilder(q.poll());
                for(int j = 0; j < l; ++j){
                    char ch = word.charAt(j);
                    for(int k = 'a'; k < 'z'; ++k){
                        if(ch == k)
                            continue;
                        word.setCharAt(j, (char)k);
                        String w = word.toString();
                        if(w.equals(endWord))
                            return step+1;
                        if(!dict.contains(w))
                            continue;
                        q.offer(w);
                        dict.remove(w);
                    }
                    word.setCharAt(j, ch);
                }
            }
        }
        return 0;
    }
}

加载全部内容