C++實現LeetCode(127.詞語階梯)

Posted on by

[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.

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

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

明確瞭要用BFS，我們可以開始解題瞭，為瞭提到字典的查找效率，我們使用HashSet保存所有的單詞。然後我們需要一個HashMap，來建立某條路徑結尾單詞和該路徑長度之間的映射，並把起始單詞映射為1。既然是BFS，我們需要一個隊列queue，把起始單詞排入隊列中，開始隊列的循環，取出隊首詞，然後對其每個位置上的字符，用26個字母進行替換，如果此時和結尾單詞相同瞭，就可以返回取出詞在哈希表中的值加一。如果替換詞在字典中存在但在哈希表中不存在，則將替換詞排入隊列中，並在哈希表中的值映射為之前取出詞加一。如果循環完成則返回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的遍歷機制就是一層一層的擴大的，那麼我們隻要記住層數就行，然後在while循環中使用一個小trick，加一個for循環，表示遍歷完當前隊列中的個數後，層數就自增1，這樣的話我們就省去瞭HashMap，而僅僅用一個變量res來記錄層數即可，參見代碼如下：

解法二：

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++實現LeetCode(127.詞語階梯)的文章就介紹到這瞭,更多相關C++實現詞語階梯內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：