亲宝软件园·资讯

展开

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

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:

  1. Only one letter can be changed at a time.
  2. 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;
    }
}

 

加载全部内容

相关教程
猜你喜欢
用户评论