[LeetCode] 127.Word Ladder 詞語(yǔ)階梯

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.

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

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

明確了要用BFS，我們可以開始解題了，為了提到字典的查找效率，我們使用HashSet保存所有的單詞。然后我們需要一個(gè)HashMap，來建立某條路徑結(jié)尾單詞和該路徑長(zhǎng)度之間的映射，并把起始單詞映射為1。既然是BFS，我們需要一個(gè)隊(duì)列queue，把起始單詞排入隊(duì)列中，開始隊(duì)列的循環(huán)，取出隊(duì)首詞，然后對(duì)其每個(gè)位置上的字符，用26個(gè)字母進(jìn)行替換，如果此時(shí)和結(jié)尾單詞相同了，就可以返回取出詞在哈希表中的值加一。如果替換詞在字典中存在但在哈希表中不存在，則將替換詞排入隊(duì)列中，并在哈希表中的值映射為之前取出詞加一。如果循環(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;
    }
};

其實(shí)我們并不需要上面解法中的HashMap，由于BFS的遍歷機(jī)制就是一層一層的擴(kuò)大的，那么我們只要記住層數(shù)就行，然后在while循環(huán)中使用一個(gè)小trick，加一個(gè)for循環(huán)，表示遍歷完當(dāng)前隊(duì)列中的個(gè)數(shù)后，層數(shù)就自增1，這樣的話我們就省去了HashMap，而僅僅用一個(gè)變量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

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

最新評(píng)論