LeetCode 127. Word Ladder [Hard] [C++] 解題筆記

 這題給我們一個字串的集合 wordList，和一個 beginWord 一個 endWord，要我們求從 beginWord 到 endWord 的"最小轉換次數"，轉換一次只能替換目前字串的其中一個字元並且轉換後的字元必須是在 wordList 中存在的。

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.

想法:

    這題和 126. Word Ladder II 一樣，直接使用 BFS，差別在於說這題只需要找最小轉換次數(最短路徑的長度)

，因此不需要將所有解記錄下來，只要找到一個解即可停止，相對簡單一點也不用 backtrace 還原路徑。

完整程式碼:

解法一(BFS):

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
        q.push(beginWord);
        unordered_set<string> mapping(wordList.begin(), wordList.end());
        int step = 0;
        if (!mapping.count(endWord)) { return step; }
        while (!q.empty()) {
            step++;
            int q_size = q.size();
            for (int i = 0; i < q_size; i++) {
                auto cur = q.front();
                q.pop();
                for (int j = 0; j < cur.size(); j++) {
                    auto c = cur[j];
                    for (int k = 'a'; k <= 'z'; k++) {
                        cur[j] = k;
                        // not contained in wordlist
                        if (mapping.find(cur) == mapping.end()) { continue; }
                        // reach target
                        if (cur == endWord) { return step + 1; }                        
                        // 不走回頭路
                        mapping.erase(cur);
                        q.push(cur);
                    }
                    cur[j] = c;
                }
            }   
        }
        return 0;
    }
};

解法二(Bidirectional BFS):

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> mapping(wordList.begin(), wordList.end());
        int step = 0;
        if (!mapping.count(endWord)) { return step; }
        
        unordered_set<string> q1{beginWord};
        unordered_set<string> q2{endWord};
        
        while (!q1.empty() && !q2.empty()) {
            ++step;
            // extend from smaller side
            if (q1.size() > q2.size()) {
                swap(q1, q2);
            }
            
            unordered_set<string> q;
            
            for (auto w : q1) {
                for (int i = 0; i < w.size(); i++) {
                    auto c = w[i];
                    for (int j = 'a'; j <= 'z'; j++) {
                        w[i] = j;
                        // reach target
                        if (q2.count(w)) { return step + 1; }
                        // 一定要在q2.count(w) 之後檢查，因為若是已經延伸到共同點，則該點應該在 q2 延伸到時就已經從 mapping中刪除。
                        // 因此先執行 mapping.count(w) 的檢查會把找到共通點的情況略掉。
                        if (!mapping.count(w)) { continue; }
                        mapping.erase(w);
                        q.emplace(w);
                    }
                    w[i] = c;
                }
            }
            swap(q, q1);
            cout<<step<<endl;
        }
        return 0;       
    }
};