LeetCode 126. 单词接龙 II

LeetCode 126. 单词接龙 II

思路：

先BFS，维护一个dist数组，dist数组是图中每个点到起点的距离，这样我们在搜索路径的时候，可以优化，避免去走到一些不在路径中的点。
我们在搜索路径DFS的时候，只去走那些 dist[end] = dist[i] + 1的点i。

代码：

class Solution {
public:
    vector<string> q;
    unordered_set<string> S;//存的是wordlist中所有的字符串
    unordered_map<string,int> dist;//到起点的距离
    vector<vector<string>> ans;
    vector<string> path;
    string beginWord;

    vector<vector<string>> findLadders(string _beginWord, string endWord, vector<string>& wordList) {
        beginWord = _beginWord;
        for(auto word:wordList) S.insert(word);
        queue<string> q;
        q.push(beginWord);
        //bfs 搜索最短路
        while(q.size()){
            auto t=q.front();
            q.pop();

            string r=t;
            //枚举t的每一位
            for(int i=0;i<t.size();i++){
                //改变t之后 下一次还需要用原始的t 所以用r去维护
                t=r;
                for(char j = 'a';j<='z';j++){
                    t[i] = j;
                    //列表中有这个 且没有被搜索过
                    if(S.count(t) && dist.count(t) == 0){
                        dist[t] = dist[r] + 1;
                        //在这里break是可以的，因为所有的字符串都是相同长度的
                        if(t == endWord) break;
                        q.push(t);
                    }
                }

            }
        }
        //如果不存在最短路就返回空
        if(dist.count(endWord) == 0) return ans;
        //把endWord加入到path中 从后往前搜 因为我们得到的dist是到起点的距离 
        //可以使用 1 + dist[t] == dist[end] 来剪枝
        path.push_back(endWord);
        dfs(endWord);
        return ans;

    }

    void dfs(string t){
        if(t == beginWord){
            //因为是倒着搜索的，所以需要反转
            reverse(path.begin(),path.end());
            ans.push_back(path);
            reverse(path.begin(),path.end());
        }
        else{
            string r = t;
            for(int i=0;i<t.size();i++){
                t = r;
                for(char j='a';j<='z';j++){
                    t[i] = j;
                    //这里是优化， 满足 dist[end] = dist[i] + 1 r是上一步的 
                    //路径中走过t这个点 而且满足 上述条件
                    if(dist.count(t) && dist[t] + 1 == dist[r]){
                        path.push_back(t);
                        dfs(t);
                        path.pop_back();
                    }
                }
            }
        }
    }
};