LeetCode - 解题笔记 - 127 - Word Ladder

LeetCode - 解题笔记 - 127 - Word Ladder Solution 1

实际上是对 0126. Word Ladder II 的变体，不需要返回路径，只需要计算层数。

• 时间复杂度： O ( N d ) O(N^d) O(Nd)，其中 N N N为wordList的长度， d d d为编辑距离，最坏的搜索范围就是每一层都是全展开，实际会有大量剪枝
• 空间复杂度： O ( d N d ) O(dN^d) O(dNd)，其中 N N N为wordList的长度， d d d为编辑距离，最坏的搜索范围就是每一层都是全展开，实际会有大量剪枝

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        // 序列中必须要有endWord
        unordered_set words = {wordList.begin(), wordList.end()};
        if (words.find(endWord) == words.end()) {
            return 0;
        }
        
        auto ans = this->bfs(beginWord, endWord, words);
            
        return ans;
    }
private:
    int bfs(string & beginWord, string & endWord, unordered_set & words) {
        
        queue q;
        q.push(beginWord);
        
        bool flag = false; // 是否向下层搜索
        unordered_set visited;
        
        int ans = 1;
        
        while (!q.empty()) {
            // 分层bfs
            int size = q.size();
            vector tempVisited; 
            while (size--) {
                auto tempWord = q.front();
                q.pop();
                
                auto mods = this->getMods(tempWord, words);
                for (auto mod: mods) {
                    if (visited.find(mod) == visited.end()) {
                        // 得是之前没出现过的单词
                        if (mod == endWord) {
                            // 正好找到endWord，搜索完当前层后终止
                            flag = true;
														break;
                        } else {
                            // 不是，保存结果路径到队列中
                            q.push(mod);
                            tempVisited.push_back(mod);
                        }
                        
                    }
                }
							  if (flag) { break; }
            }
            
            ans++;
            if (flag) { break; }
            
            visited.insert(tempVisited.begin(), tempVisited.end());
        }
        
        return flag? ans: 0;
    }
    
    
    vector getMods (string word, unordered_set & words) {
        vector mods;
        
        for (int index = 0; index < word.size(); ++index) {
            auto temp = word[index];
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                
                if (temp != ch) {
                    word[index] = ch;
                    if (words.find(word) != words.end()) {
                        mods.push_back(word);
                    }
                }
    
            }
            word[index] = temp;
        }
        
        return mods;
    }
};

Solution 2

可惜的是，上述改动实现用于python时会TLE，因此不得已得学一下双向BFS了。区别于传统BFS，双向BFS就是在终点一直的前提下，同时从起点和终点进行BFS，从而有效地减小搜索空间，节省时间。参考实现为：广度优先遍历、双向广度优先遍历（Java） - 单词接龙 - 力扣（LeetCode） (leetcode-cn.com)

整体框架没有变化，做了一些调整：

1. 由于本身实现的时分层BFS，因此队列的具体实现不用queue也可，考虑到中间要不断查询是否相遇，因此参考题解换成了哈希表
2. 判定条件的调整，之前的实现是对每一个没出现过的单词进行检查，并且到endWord终止。这里要调整为对所有可能出现过的进行考察，到相遇为止，搜索过程中更新visited

• 时间复杂度： O ( N d 2 ) O(N^{frac d2}) O(N2d​)，其中 N N N为wordList的长度， d d d为编辑距离，最坏的搜索范围就是每一层都是全展开，双向搜索可以让时间减半
• 空间复杂度： O ( N d 2 ) O(N^{frac d2}) O(N2d​)，其中 N N N为wordList的长度， d d d为编辑距离，最坏的搜索范围就是每一层都是全展开，双向搜索可以让时间减半

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        // 序列中必须要有endWord
        unordered_set words = {wordList.begin(), wordList.end()};
        if (words.find(endWord) == words.end()) {
            return 0;
        }
        
        auto ans = this->dualBfs(beginWord, endWord, words);
            
        return ans;
    }
private:
    
    int dualBfs(string & beginWord, string & endWord, unordered_set & words) {
        
        unordered_set qA, qB;
        qA.insert(beginWord);
        qB.insert(endWord);
        
        bool flag = false; // 是否向下层搜索
        unordered_set visited;
        
        int ans = 1;
        
        while (!qA.empty() && !qB.empty()) {
            // 分层bfs
            
            if (qA.size() > qB.size()) {
                // 双向BFS，总是扩展少的那一侧
                auto qT = qA;
                qA = qB;
                qB = qT;
            }
            unordered_set tempVisited; 
            for (auto tempWord: qA) {
                auto mods = this->getMods(tempWord, words);
                for (auto mod: mods) {
                    
                    if (qB.find(mod) != qB.end()) {
                        // 相遇
                        flag = true;
                        break;
                    } else if (visited.find(mod) == visited.end()) {
                        tempVisited.insert(mod);
                        visited.insert(mod);
                    }
                }
                if (flag) { break; }
            }
            
            ans++;
            if (flag) { break; }
            qA = tempVisited;
        }
        
        
        return flag? ans: 0;
    }
    
    
    vector getMods (string word, unordered_set & words) {
        vector mods;
        
        for (int index = 0; index < word.size(); ++index) {
            auto temp = word[index];
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                
                if (temp != ch) {
                    word[index] = ch;
                    if (words.find(word) != words.end()) {
                        mods.push_back(word);
                    }
                }
    
            }
            word[index] = temp;
        }
        
        return mods;
    }
};

Solution 3

Solution 2的Python实现

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        def bfs() -> int:
            nonlocal beginWord, endWord, wordList, ans
            
            qA, qB = set(), set()
            qA.add(beginWord)
            qB.add(endWord)
            
            flag = False
            visited = set()
            
            ans = 1
            while len(qA) > 0 and len(qB) > 0:
                if len(qA) > len(qB):
                    qA, qB = qB, qA
                
                tempVisited = set()
                
                for tempWord in qA:
                    mods = getMods(tempWord)
                    for mod in mods:
                        if mod in qB:
                            flag = True
                            break
                        elif mod not in visited:
                            tempVisited.add(mod)
                            visited.add(mod)
                                
                    if flag: break
                
                ans += 1
                if flag: break
                qA = tempVisited
                
            return ans if flag else 0
            
        def getMods(word: str) -> List[str]:
            nonlocal wordList
            
            mods = list()
            word_list = list(word)
            for i in range(len(word)):
                temp = word_list[i]
                for ch in string.ascii_lowercase:
                    word_list[i] = ch
                    newWord = ''.join(word_list)
                    if newWord in wordList:
                        mods.append(newWord)
                        
                
                word_list[i] = temp
                
            return mods
        
        
        ans = 0
        
        if endWord not in wordList: return ans
        
        ans = bfs()
        
        return ans