Leetcode 126 Solution

class Solution {
    vector<vector<string>> res;

public:
    void generate_result(const string& beginWord, const string& curr, vector<string>& path, unordered_map<string, vector<string>>& last_hops)
    {
        path.push_back(curr);

        if (beginWord == curr)
        {
            vector<string> path_res = path;
            reverse(path_res.begin(), path_res.end());
            res.push_back(path_res);
            path.pop_back();
            return;
        }

        auto prevs = last_hops[curr];
        for (auto prev : prevs)
            generate_result(beginWord, prev, path, last_hops);

        path.pop_back();
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        unordered_map<string, vector<string>> last_hops;

        queue<string> q;
        q.push(beginWord);

        wordList.erase(beginWord);

        int step = 1;

        while (q.empty() == false)
        {
            int s = q.size();
            step++;

            set<string> next;
            for (int i = 0; i < s; i++)
            {
                auto str = q.front();
                q.pop();

                bool found = false;
                for (int j = 0; j < str.size(); j++)
                {
                    for (char ch = 'a'; ch <= 'z'; ch++)
                    {
                        if (ch == str[j])
                            continue;

                        auto next_str = str;
                        next_str[j] = ch;

                        if (next_str == endWord)
                        {
                            vector<string> path;
                            path.push_back(endWord);
                            generate_result(beginWord, str, path, last_hops);
                            found = true;
                            break;
                        }

                        if (wordList.find(next_str) != wordList.end())
                        {
                            if (last_hops.find(next_str) == last_hops.end())
                                last_hops[next_str] = vector<string>();
                            last_hops[next_str].push_back(str);

                            next.insert(next_str);
                        }
                    }

                    if (found)
                        break;
                }
            }

            if (res.size())
                break;

            for (auto& str : next)
            {
                wordList.erase(str);
                q.push(str);
            }
        }

        return res;
    }
};