題目網址：https://leetcode.cn/problems/word-ladder/

題意：一個 transform sequence 指的是 wordList 中從單字 beginWord 到 endWord 的 sequence beginWord -> s1 -> s2 -> ... -> sk, 且 transform sequence 需滿足以下條件：

  • 相鄰的兩個單字只差一個字母
  • 每個 si 都在 wordList 中, 其中 1 ≤ i ≤ k。注意, beginWord 不需在 wordList 中
  • sk == endWord

給兩個單字 beginWord 和 endWord, 以及一字典 wordList, 返回從 beginWord 到 endWord 的最短 transform sequence 中的單字個數。若不存在這樣的 transform sequence, 則返回 0。

注意：wordList[i] 僅由小寫字母所組成。

Solution 1：

想法：看到最短路徑會直覺想到 Dijkstra, 但在 unweighted graph 中, 其實只需要用 BFS 就可求得最短路徑了。故利用 BFS, 從 queue q 中取出當前的 word curWord, 然後將每個 curWord[i] 替換成 a - z 的其他 char。若更改後的 curWord 存在於 dict 中, 則將其加到 q 中, 並將其從 dict 中刪除以避免下一輪中 q 重複添加

e.g. hit -> hot -> hit

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 將 wordList 轉成 hash set 方便查找
        unordered_set<string> dict(wordList.begin(), wordList.end());

        // 若 endWord 不在 dict 中, 則返回 0
        if (dict.find(endWord) == dict.end()) {
            return 0;
        }

        int res = 0, len = beginWord.size();
        queue<string> q({beginWord});

        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                const auto curWord = q.front();
                q.pop();

                for (int j = 0; j < len; ++j) {
                    const auto ch = curWord[j]; // 記住當前第 j 位的 char, 等等要還原

                    for (char c = 'a'; c <= 'z'; ++c) {
                        curWord[j] = c; // 變更第 j 位的 char 為 c

                        // 若變更完後為 endWord, 則直接返回 res + 1
                        if (curWord == endWord) {
                            return res + 1;
                        }

                        // 若變更完後的 word 在 dict 中, 則將其加到 q 中
                        if (dict.find(curWord) != dict.end()) {
                            q.emplace(curWord);
                            dict.erase(curWord); // 刪除當前 word, 避免下一輪重複添加
                        }
                    }

                    curWord[j] = ch; // 還原回原先的 word
                }
            }
        }
        return 0; // not found
    }
};
  • time：$O(n \cdot len)$ ➔ $O(n \cdot 26 \cdot len)$, 其中 n 為 word 的個數, len 為每個 word 的長度
    • $O(n)$：每一輪最少要從 wordList 中取一個 word, 故最多有 n 輪, 總共最多取 n 個 word
    • $O(26 \cdot len)$：每個 word 可產生 $26 * len$ 個單字
  • space：$O(n \cdot len)$ ➔ dict 儲存每個 word

Solution 2：

想法：利用 Bidirectional BFS（雙向 BFS）, 從 beginWord 和 endWord 兩端開始拓展, 兩端產生的 word 分別用 s1、s2 儲存, 讓 s1 永遠為較小的 hash set, 這樣 for loop 進行拓展的 word 會比較少。一旦 s1 的 word 所拓展出來的 new word 出現在 s2 中, 代表兩端碰頭, 故返回 res + 1

e.g. wordList = ["hot","dot","dog","lot","log","cog"], begin = "hit", end = "cog"

  • 一開始, s1 = {hit}, s2 = {cog}
  • 第一輪, s1 拓展 ➔ s1 = {hit, hot}, s2 = {cog}
  • 第二輪
    • s1 和 s2 先 swap ➔ s1 = {cog}, s2 = {hit, hot}
    • s1 拓展 ➔ s1 = {cog, dog, log}, s2 = {hit, hot}
  • 第三輪
    • s1 和 s2 先 swap ➔ s1 = {hit, hot}, s2 = {cog, dog, log}
    • s1 拓展 ➔ s1 = {hit, hot, dot, lot}, s2 = {cog, dog, log}
  • 第四輪
    • s1 和 s2 先 swap ➔ s1 = {cog, dog, log}, s2 = {hit, hot, dot, lot}
    • s1 拓展 ➔ s1 = {cog, dog, log, dot}, 發現 dot 已出現在 s2 中, 故中止
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 將 wordList 轉成 hash set 方便查找
        unordered_set<string> dict(wordList.begin(), wordList.end());

        // 若 endWord 不在 dict 中, 則返回 0
        if (dict.find(endWord) == dict.end()) {
            return 0;
        }

        int res = 0
        const int len = beginWord.size();
        unordered_set<string> s1({beginWord});
        unordered_set<string> s2({endWord});

        while (!s1.empty() && !s2.empty()) {
            ++res;

            // 讓 s1 永遠是較小的 hash set, 這樣下面 for loop 會比較快結束
            if (s1.size() > s2.size()) {
                swap(s1, s2);
            }

            unordered_set<string> tmpSet; // 紀錄由 curWord 產生的所有 new word

            for (auto curWord : s1) { // set 中的元素為 const, 禁止用 auto& 直接修改
                for (int i = 0; i < len; ++i) {
                    const auto ch = curWord[i]; // 記住當前第 i 位的 char, 等等要還原

                    for (char c = 'a'; c <= 'z'; ++c) {
                        curWord[i] = c; // 變更第 i 位的 char 為 c

                        // 若變更完後的 word 在 s2 中, 則直接返回 res + 1
                        if (s2.find(curWord) != s2.end()) {
                            return res + 1;
                        }

                        // 變更完後的 word 在 dict 中, 則將其加到 tmpSet 中
                        if (dict.find(curWord) != dict.end()) {
                            tmpSet.emplace(curWord);
                            dict.erase(curWord); // 刪除當前 word, 避免下一輪重複拜訪
                        }
                    }

                    curWord[i] = ch; // 還原回原先的 word
                }
            }

            swap(s1, tmpSet); // s1 更新成由 curWord 產生的 word set
        }

        return 0; // not found
    }
};
  • time：$O(n \cdot len)$ ➔ $O(n \cdot 26 \cdot len)$, 其中 n 為 word 的個數, len 為每個 word 的長度
    • $O(n)$：每一輪最少要從 wordList 中取一個 word, 故最多有 n 輪, 總共最多取 n 個 word
    • $O(26 \cdot len)$：每個 word 可產生 $26 * len$ 個單字
  • space：$O(n \cdot len)$ ➔ dict 儲存每個 word