LeetCode 0126 - Word Ladder II

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
    [
        ["hit","hot","dot","dog","cog"],
        ["hit","hot","lot","log","cog"]
    ]

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

class Solution {
public:
    vector<vector<string>> findLadders(const string& beginWord, const string& endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        unordered_set<string> words;
        queue<vector<string>> paths;
        paths.push(vector<string>{beginWord});
        int step = 1;
        int minStep = INT_MAX;
        while(!paths.empty()) {
            vector<string> currentPath = paths.front();
            paths.pop();
            if(currentPath.size() > step) {
                for(const string &word : words)
                    dict.erase(word);
                words.clear();
                step = currentPath.size();
                if(step > minStep)
                    break;
            }
            string lastWord = currentPath.back();
            for(int i = 0; lastWord[i]; i++) {
                string tmpWord = lastWord;
                for(char ch = 'a'; ch <= 'z'; ch++) {
                    tmpWord[i] = ch;
                    if(!dict.count(tmpWord))
                        continue;
                    words.insert(tmpWord);
                    vector<string> nextPath = currentPath;
                    nextPath.push_back(tmpWord);
                    if(tmpWord == endWord)
                        res.push_back(nextPath), minStep = min(minStep, (int)nextPath.size());
                    else
                        paths.push(nextPath);
                }
            }
        }
        return res;
    }
};