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

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

推薦閱讀: