[LeetCode] 127.Word Ladder 詞語階梯

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 beginWord is 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.

這道詞句階梯的問題給了我們一個單詞字典，里面有一系列很相似的單詞，然后給了一個起始單詞和一個結束單詞，每次變換只能改變一個單詞，并且中間過程的單詞都必須是單詞字典中的單詞，讓我們求出最短的變化序列的長度。這道題還是挺有難度的，我當然是看了別人的解法才寫出來的，這沒啥的，從不會到完全掌握才是成長嘛～

當拿到題就懵逼的我們如何才能找到一個科學的探索解題的路徑呢，那就是先別去管代碼實現(xiàn)，如果讓我們肉身解題該怎么做呢？讓你將 'hit' 變?yōu)?'cog'，那么我們發(fā)現(xiàn)這兩個單詞沒有一個相同的字母，所以我們就嘗試唄，博主會先將第一個 'h' 換成 'c'，看看 'cit' 在不在字典中，發(fā)現(xiàn)不在，那么把第二個 'i' 換成 'o'，看看 'hot' 在不在，發(fā)現(xiàn)在，完美！然后嘗試 'cot' 或者 'hog'，發(fā)現(xiàn)都不在，那么就比較麻煩了，我們沒法快速的達到目標單詞，需要一些中間狀態(tài)，但我們怎么知道中間狀態(tài)是什么。簡單粗暴的方法就是brute force，遍歷所有的情況，我們將起始單詞的每一個字母都用26個字母來替換，比如起始單詞 'hit' 就要替換為 'ait', 'bit', 'cit', .... 'yit', 'zit'，將每個替換成的單詞都在字典中查找一下，如果有的話，那么說明可能是潛在的路徑，要保存下來。那么現(xiàn)在就有個問題，比如我們換到了 'hot' 的時候，此時發(fā)現(xiàn)在字典中存在，那么下一步我們是繼續(xù)試接下來的 'hpt', 'hqt', 'hrt'... 還是直接從 'hot' 的首字母開始換 'aot', 'bot', 'cot' ... 這實際上就是BFS和DFS的區(qū)別，到底是廣度優(yōu)先，還是深度優(yōu)先。講到這里，不知道你有沒有覺得這個跟什么很像？對了，跟迷宮遍歷很像啊，你想啊，迷宮中每個點有上下左右四個方向可以走，而這里有26個字母，就是二十六個方向可以走，本質上沒有啥區(qū)別??！如果熟悉迷宮遍歷的童鞋們應該知道，應該用BFS來求最短路徑的長度，這也不難理解啊，DFS相當于一條路走到黑啊，你走的那條道不一定是最短的啊。而BFS相當于一個小圈慢慢的一層一層擴大，相當于往湖里扔個石頭，一圈一圈擴大的水波紋那種感覺，當水波紋碰到湖上的樹葉時，那么此時水圈的半徑就是圓心到樹葉的最短距離。腦海中有沒有浮現(xiàn)出這個生動的場景呢？

明確了要用BFS，我們可以開始解題了，為了提到字典的查找效率，我們使用HashSet保存所有的單詞。然后我們需要一個HashMap，來建立某條路徑結尾單詞和該路徑長度之間的映射，并把起始單詞映射為1。既然是BFS，我們需要一個隊列queue，把起始單詞排入隊列中，開始隊列的循環(huán)，取出隊首詞，然后對其每個位置上的字符，用26個字母進行替換，如果此時和結尾單詞相同了，就可以返回取出詞在哈希表中的值加一。如果替換詞在字典中存在但在哈希表中不存在，則將替換詞排入隊列中，并在哈希表中的值映射為之前取出詞加一。如果循環(huán)完成則返回0，參見代碼如下：

解法一：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;
        unordered_map<string, int> pathCnt{{{beginWord, 1}}};
        queue<string> q{{beginWord}};
        while (!q.empty()) {
            string word = q.front(); q.pop();
            for (int i = 0; i < word.size(); ++i) {
                string newWord = word;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newWord[i] = ch;
                    if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
                    if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
                        q.push(newWord);
                        pathCnt[newWord] = pathCnt[word] + 1;
                    }   
                }
            }
        }
        return 0;
    }
};

其實我們并不需要上面解法中的HashMap，由于BFS的遍歷機制就是一層一層的擴大的，那么我們只要記住層數(shù)就行，然后在while循環(huán)中使用一個小trick，加一個for循環(huán)，表示遍歷完當前隊列中的個數(shù)后，層數(shù)就自增1，這樣的話我們就省去了HashMap，而僅僅用一個變量res來記錄層數(shù)即可，參見代碼如下：

解法二：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (!wordSet.count(endWord)) return 0;
        queue<string> q{{beginWord}};
        int res = 0;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                string word = q.front(); q.pop();
                if (word == endWord) return res + 1;
                for (int i = 0; i < word.size(); ++i) {
                    string newWord = word;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        newWord[i] = ch;
                        if (wordSet.count(newWord) && newWord != word) {
                            q.push(newWord);
                            wordSet.erase(newWord);
                        }   
                    }
                }
            }
            ++res;
        }
        return 0;
    }
};

類似題目：

Word Ladder II

Minimum Genetic Mutation

參考資料：

https://leetcode.com/problems/word-ladder/description/

https://leetcode.com/problems/word-ladder/discuss/40728/Simple-Java-BFS-solution-with-explanation

到此這篇關于C++實現(xiàn)LeetCode(127.詞語階梯)的文章就介紹到這了,更多相關C++實現(xiàn)詞語階梯內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論