LeetCode126 单词接龙II

链接: https://leetcode-cn.com/problems/word-ladder-ii/description/

题意

给定一个起始字符串和一个终止字符串，以及一个单词表，求是否可以将起始字符串每次改一个字符，直到改成终止字符串，且所有中间的修改过程表示的字符串都可以在单词表里找到。
输出需要修改次数最少的所有更改方式

解法

本题的难度是Hard，难点在于搜索过程中的优化
我们可以将这道题抽象成一个图，每个单词就是图中的一个结点
如果两个字符串只有一个字母不同，则这两个结点之间有一条边相连
建图的过程使用广度优先搜索，在建完以后进行回溯找出所有的路径
在实现上也有一些难点和可以学习的地方，代码也做了详细的注释
例如使用一个数组标记是否入队，遍历整个队列的for循环处理

有一个重点是，需要将图建成一个有向图
由于是BFS，所以会将队列中所有元素全拿出来进行建图，为了不产生走回头路的情况
结点之间只会是单项边
如果一个结点已经被访问过了，它就会被从单词表中去除

为了查找的高效，将单词表转成set进行处理
有一些count, erase和find的操作也需要熟练

在找某个字符串所有的邻居时，除了遍历所有字符串以外，还可以替换单词中的每一个字符，在单词表大的情况下可以降低计算复杂度

BFS建图完成后回溯完成路径的匹配，这是针对这一题而言的

对于单词接龙这一题而言，由于其只需要找到最短的路径长度，所以在BFS过程中只要找到目标字符串就可以结束

代码

126 单词接龙II

class Solution {
public:
    vector<vector<string>> ans; // 存储答案
    map<string, vector<string>> graph; // 存储图
    vector<string> curPath; // 存储当前路径
    vector<string> findNeighbors(string& word, unordered_set<string>& wordList) {
        vector<string> ret;
        for (int i = 0; i < word.size(); i++) {
            char oldChar = word[i]; // 替换每一个字符
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch == oldChar) {
                    continue;
                }
                word[i] = ch;
                if (wordList.count(word)) {
                    ret.push_back(word);
                }
            }
            word[i] = oldChar; // 修改回原单词
        }
        return ret;
    }

    void backtrack(string& nowWord, string& endWord) {
        if (nowWord == endWord) { // 回溯寻找
            ans.push_back(curPath);
            return;
        }
        for (auto word: graph[nowWord]) {
            curPath.push_back(word);
            backtrack(word, endWord);
            curPath.pop_back();
        }
    }

    void bfs(string& beginWord, string& endWord, unordered_set<string>& wordList) {
        queue<string> q;
        // 将beginWord从单词表中去除
        if (wordList.count(beginWord)) { 
            wordList.erase(wordList.find(beginWord));
        }

        map<string, int> isEnqueued;
        q.push(beginWord);
        isEnqueued[beginWord] = 1;

        while(q.size()) {
            vector<string> vis;
            for (int i = q.size() - 1; i >= 0; i--) {
                // 遍历队列的for处理
                    string word = q.front();
                    q.pop();
                    vector<string> ret = findNeighbors(word, wordList);
                    // 找出word的所有邻居
                    for (auto idx: ret) {
                        graph[word].push_back(idx); // 建图
                        vis.push_back(idx); // 节点标记访问
                        if (isEnqueued[idx] == 0) {
                            isEnqueued[idx] = 1;
                            q.push(idx); // 如果该单词未被加入队列则入队
                        }
                    }
            }
            for (auto word: vis) {
                // 去除所有已经被访问到的元素 以防产生双向边
                if (wordList.count(word)) {
                // 学习从set中erase单词的写法
                    wordList.erase(wordList.find(word));
                }
            }

        }
    }
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> newWordList(wordList.begin(), wordList.end());
        bfs(beginWord, endWord, newWordList);
        curPath = {beginWord};
        backtrack(beginWord, endWord);
        return ans;

    }
};