Word Ladder II

WordLadderII.cpp

class Solution {
public:
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string> > result;
        unordered_set<string> visited;
        unordered_map<string, vector<string> > traces;
        unordered_set<string> curr;
        curr.insert(start);
        dict.insert(end);
        visited.insert(start);
        while (!curr.empty() && !curr.count(end) ) {
            unordered_set<string> next;
            for (auto it = curr.begin(); it != curr.end(); ++it)
                visited.insert(*it);
            for (auto it = curr.begin(); it != curr.end(); ++it) {
                string word = *it;
                for (int i = 0; i < it->length(); ++i) {  
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c != word[i]) {
                            swap(c, word[i]);
                            if (!visited.count(word) && dict.count(word)) {
                                traces[word].push_back(*it);
                                next.insert(word);
                            }
                            swap(c, word[i]);
                        }
                    }
                }
            }
            curr.swap(next);
        }
        if (curr.size()) {
            vector<string> path;
            buildPath(traces, path, start, end, result);
        }
        return result;
    }
private:
    void buildPath(unordered_map<string, vector<string> > &traces, 
            vector<string> &path, const string &from, const string &word, 
            vector<vector<string> > &result) {
        path.push_back(word);
        if (word == from) {
            result.push_back(path);
            reverse(result.back().begin(), result.back().end());
        } else {
            for (auto it = traces[word].begin(); it != traces[word].end(); it++) {
                buildPath(traces, path, from, *it, result);
            }
        }
        path.pop_back();
    }
};