LeetCode 题解
    单词阶梯系列

    单词阶梯系列

    题目1描述：给定起始词和终止词，以及一个单词表，找到起始词每次只能变一个字母且中间词必须在字典里，返回最小变换次数

    核心思路

    1. 根据定义构建邻接表，然后进行宽搜，找到终止词或搜索结束后返回结果即可

    时间复杂度：N² + N 空间复杂度：N²

    class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        map<string, vector<string> > g;
        construct_graph(beginWord, wordList, g);
        return BFS(beginWord, endWord, g);
    }
    
	// 宽搜
    int BFS(string &beginWord, string &endWord,
           map<string, vector<string> >& graph) {
        queue<pair<string, int> > Q;
        unordered_set<string> visit;
        Q.push(make_pair(beginWord, 1));
        visit.insert(beginWord);
        while(!Q.empty()) {
            string node = Q.front().first;
            int step=Q.front().second;
            Q.pop();
            if (node == endWord) return step;
            const vector<string> &neighbors = graph[node];
            for(int i=0;i<neighbors.size();++i) {
				// 继续搜索没有搜过的节点
                if (visit.find(neighbors[i])==visit.end()) {
                    Q.push(make_pair(neighbors[i], step+1));
                    visit.insert(neighbors[i]);
                }
            }
        }
        return 0;
    }
    
	// 构建邻接表 map+vector
    void construct_graph(string &beginWord,
                        vector<string>& wordList,
                        map<string, vector<string> >& graph) {
        wordList.push_back(beginWord);
        for(int i=0;i<wordList.size();++i) {
            graph[wordList[i]] = vector<string>();
        }
        for(int i=0;i<wordList.size();++i) {
            for(int j=i+1;j<wordList.size();++j) {
                if (connect(wordList[i], wordList[j])) {
					// i 于 j 无向相连
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
        }
    }
    
	// 判断是否为相邻节点（是否只有一个字母不同）
    bool connect(const string& word1, const string& word2) {
        int cnt=0;
        for(int i=0;i<word1.size()&&cnt<2;++i)
            if (word1[i]!=word2[i]) ++cnt;
        return cnt==1;
    }
};
    1. 双向 BFS ，依次暴力更改每一个词的每一个字母，可以大幅降低每层需要检查的单词个数，每次优先探索数量少的队列
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (dict.find(endWord)==dict.end()) return 0;

    int step=0;
	// 因为双向BFS需要对另一个队列的元素进行查找，使用 set 使得查询效率提升
    unordered_set<string> q1{beginWord};
    unordered_set<string> q2{endWord};
    unordered_set<string> tmp;
    while(!q1.empty() && !q2.empty()) {
        ++step;
        if (q1.size()>q2.size()) swap(q1, q2);
        tmp.clear();
        for(string w : q1) {
            for(int i=0;i<w.size();++i) {
                char oldc=w[i];
                for(int j='a';j<='z';++j) {
                    w[i]=j;
					// 双向搜索碰头，搜索结束
                    if (q2.find(w)!=q2.end()) return step+1;
					// 已访问过
                    if (dict.find(w)==dict.end()) continue;
					// 加入访问容器中，同时在单词表中删除
                    tmp.insert(w);
                    dict.erase(w);
                }
                w[i]=oldc;
            }
        }
        swap(tmp, q1);
    }

    return 0;
}

    相似问题

    题目2描述：同样是寻找最小变换，但是需要返回所有的最短变换的路径

    难点分析

    问题转化为：如何记录所有宽搜的最短路径？

    1. 正常宽搜使用的队列都是将下一个需要搜寻的目标入队，当前搜寻的出队之后就没有记录了，这就需要对原有的队列进行改造

    改造方案：vector 模拟队列，每个元素需要存储上一个元素的下标以及当前元素的步数和内容，类似静态链表，当找到最小步数的时候入队即可

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        if (wordList.size()==0) return res;
        map<string, vector<string> > g;
        construct_graph(beginWord, wordList, g);
        vector<Qitem> Q;
        vector<int> end_pos;
        BFS(beginWord, endWord, g, Q, end_pos);
        for(int i=0;i<end_pos.size();++i) {
            int pos = end_pos[i];
            vector<string> path;
            while(pos!=-1) {
                path.push_back(Q[pos].node);
                pos=Q[pos].parent_pos;
            }
            res.push_back(vector<string>());
            for(int j=path.size()-1;j>=0;--j) res[res.size()-1].push_back(path[j]); 
        }
        return res;
    }
    
    struct Qitem {
        string node;
        int parent_pos;
        int step;
        Qitem(string _node, int _parent_pos, int _step) : node(_node), parent_pos(_parent_pos), step(_step) {}
    };
    
    void BFS(string &beginWord, string &endWord,
            map<string, vector<string> > &graph,
            vector<Qitem> &Q,
            vector<int> &end_word_pos) {
        map<string, int> visit;
        int min_step=0;
        Q.push_back(Qitem(beginWord.c_str(), -1, 1));
        visit[beginWord]=1;
        int front=0;
        while(front!=Q.size()) {
            const string &node = Q[front].node;
            int step=Q[front].step;
            if (min_step != 0 && step>min_step) break;
            if (node==endWord) {
                min_step=step;
                end_word_pos.push_back(front);
            }
            const vector<string> &neighbors = graph[node];
            for(int i=0;i<neighbors.size();++i) {
                if (visit.find(neighbors[i])==visit.end() || visit[neighbors[i]]==step+1) {
                    Q.push_back(Qitem(neighbors[i], front, step+1));
                    visit[neighbors[i]]=step+1;
                }
            }
            ++front;
        }
        
    }
    
    void construct_graph(string &beginWord,
                        vector<string>& wordList,
                        map<string, vector<string> >& graph) {
        bool hasBeginWord = false;
        for(int i=0;i<wordList.size();++i) {
            if (wordList[i]==beginWord) hasBeginWord=true;
            graph[wordList[i]] = vector<string>();
        }
        for(int i=0;i<wordList.size();++i) {
            for(int j=i+1;j<wordList.size();++j) {
                if (connect(wordList[i], wordList[j])) {
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
            if (!hasBeginWord && connect(beginWord, wordList[i]))
                graph[beginWord].push_back(wordList[i]);
        }
    }
    
    bool connect(const string& word1, const string& word2) {
        int cnt=0;
        for(int i=0;i<word1.size();++i)
            if (word1[i]!=word2[i]) ++cnt;
        return cnt==1;
    }
};

    上述解法需要事先构建好图并用 vector 模拟一个更复杂的队列，浪费了许多空间

    1. 使用 map 来构建最短路径的图，然后 DFS 找出所有路径即可

    单向 BFS

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord)==dict.end()) return res;
        dict.erase(endWord);
        bool found = false;
        unordered_set<string> q{beginWord}, tmp;
		// 最短路径图
        unordered_map<string, vector<string> > graph;
        int len = beginWord.size();
        while(!q.empty() && !found) {
			// 访问标记
            for(const string& w : q)
                dict.erase(w);

            for(const string& w : q) {
                string word = w;
                for(int i=0;i<len;++i) {
                    char oldch = word[i];
                    for(int j='a';j<='z';++j) {
                        word[i]=j;
                        if (word == endWord) {
							// 已找到末尾词本层搜索结束后退出
                            found=true;
							// w 与 word 是相邻接点
                            graph[w].push_back(word);
                        } else if (dict.find(word)!=dict.end() && !found) {
                            tmp.insert(word);
                            graph[w].push_back(word);
                        }
                    }
                    word[i]=oldch;
                }
            }
            
            swap(q, tmp);
            tmp.clear();
        }
        
        if (found) {
            vector<string> path{beginWord};
			// 递归回溯生成所有路径
            DFS(beginWord, endWord, graph, path, res);
        }
        return res;
    }
    
private:
    void DFS(const string &word, const string& endWord, const unordered_map<string, vector<string>>& g,
            vector<string>& path,
            vector<vector<string>>& res) {
        if (path.back()==endWord) {
            res.push_back(path);
            return;
        }
        
        if (g.find(word)==g.end()) return;
        
        for(auto child : g.at(word)) {
            path.push_back(child);
            DFS(child, endWord, g, path, res);
            path.pop_back();
        }
    }
};

    双向 BFS

    class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord)==dict.end()) return res;
        dict.erase(endWord);
        bool found = false;
        bool backward = false;
        unordered_set<string> q{beginWord}, p{endWord}, tmp;
        unordered_map<string, vector<string> > graph;
        int len = beginWord.size();
        while(!q.empty() && !p.empty() && !found) {
            for(const string& w : q)
                dict.erase(w);
            for(const string& w : q)
                dict.erase(w);
            
			// 双队列交换时注意连接关系的反转
            if (q.size() > p.size()) {
                swap(q, p);
                backward=!backward;
            }
            
            for(const string& w : q) {
                string word = w;
                for(int i=0;i<len;++i) {
                    char oldch = word[i];
                    for(int j='a';j<='z';++j) {
                        word[i]=j;
                        if (p.find(word) != p.end()) {
                            found=true;
                            if (!backward)
                                graph[w].push_back(word);
                            else
                                graph[word].push_back(w);
                        } else if (dict.find(word)!=dict.end() && !found) {
                            tmp.insert(word);
                            if (!backward)
                                graph[w].push_back(word);
                            else
                                graph[word].push_back(w);
                        }
                    }
                    word[i]=oldch;
                }
            }
            
            swap(q, tmp);
            tmp.clear();
        }
        
        if (found) {
            vector<string> path{beginWord};
            DFS(beginWord, endWord, graph, path, res);
        }
        return res;
    }
    
private:
    void DFS(const string &word, const string& endWord, const unordered_map<string, vector<string>>& g,
            vector<string>& path,
            vector<vector<string>>& res) {
        if (path.back()==endWord) {
            res.push_back(path);
            return;
        }
        
        if (g.find(word)==g.end()) return;
        
        for(auto child : g.at(word)) {
            path.push_back(child);
            DFS(child, endWord, g, path, res);
            path.pop_back();
        }
    }
};

    收获

    1. 双向 BFS 降低搜索层次数
    2. 当需要能够遍历和查询的队列时可以使用 set 代替 queue

    #面试 #双广搜 #BFS

    常用 STL 操作二叉树与链表专题