[宽度优先搜索] leetcode 126 Word Ladder II

class Solution {
public:
    bool CanTransform(const string& s1, const string& s2)
    {
        int count = 0;
        for(int i = 0;i < s1.size();i++)
        {
            if(s1[i] != s2[i])
            {
                count++;
            }
            if(count > 1) return false;
        }
        return count == 1;
    }
    
    unordered_map<string, unordered_set<string>> path;
    vector<vector<string>> res;
    vector<string> ans;
    void dfs(const string& word)
    {
        ans.push_back(word);
        if(path.find(word) == path.end())
        {
            if(ans.size() >= 2)
            {
                res.push_back(ans);
            }
        }
        else
        {
            for(auto& next : path[word])
            {
                dfs(next);
            }
        }
        ans.pop_back();         
    }
    
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {      
        unordered_map<string, unordered_set<string>> graph;
        wordList.push_back(beginWord);
        bool bFind = false;
        for(int i = 0;i < wordList.size(); i++)
        {
            for(int j = i + 1;j < wordList.size(); j++)
            {
                if(CanTransform(wordList[i], wordList[j]))
                {
                    graph[wordList[i]].insert(wordList[j]);
                    graph[wordList[j]].insert(wordList[i]);
                }
            }
            if(wordList[i] == endWord) bFind = true;
        }
        
        if(!bFind) return res;
        
        unordered_set<string> visit;
        unordered_map<string, int> layer;
        
        queue<string> q;
        
        q.push(beginWord);
        visit.insert(beginWord);
        bool flag = false;
        
        int count = 0;
        while(!q.empty())
        {
            int size = q.size();
            while(size--)
            {
                string cur = q.front();
                q.pop();
                for(auto& word : graph[cur])
                {
                    if(word == endWord)
                    {
                        path[word].insert(cur);
                        flag = true;
                    }
                    if(visit.find(word) == visit.end())
                    {
                        visit.insert(word);
                        q.push(word);
                        layer[word] = count;
                        path[word].insert(cur);
                    }
                    else if(layer[word] == layer[cur] + 1)
                    {
                        path[word].insert(cur);
                    }
                }
            }
            count++;
            if(flag) break;
        }
        dfs(endWord);
        for(int i = 0; i < res.size();i++)
        {
            reverse(res[i].begin(), res[i].end());
        }
        return res;
    }
};