leetcode@ [126] Word Ladder II (BFS + 层次遍历 + DFS)

https://leetcode.com/problems/word-ladder-ii/

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

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

Return

  [

    ["hit","hot","dot","dog","cog"],

    ["hit","hot","lot","log","cog"]

  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

class Solution {

public:

    void dfs(vector<vector<string> >& res, unordered_map<string, vector<string> >& fa, vector<string> load, string beginWord, string curWord) {

        if(curWord == beginWord) {

            reverse(load.begin(), load.end());

            res.push_back(load);

            reverse(load.begin(), load.end());

            return;

        }

        for(int i=; i<fa[curWord].size(); ++i) {

            load.push_back(fa[curWord][i]);

            dfs(res, fa, load, beginWord, fa[curWord][i]);

            load.pop_back();

        }

    }

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

        vector<vector<string> > res;

        if(beginWord.compare(endWord) == )  return res;

        wordList.insert(endWord);

        unordered_map<string, vector<string> > fa;

        unordered_set<string> vis;

        unordered_set<string> lev;

        unordered_set<string> next_lev;

        lev.insert(beginWord);

        bool found = false;

        while(!lev.empty() && !found) {

            if(lev.find(endWord) != lev.end())  found = true;

            for(auto str: lev)  vis.insert(str);

            for(auto str : lev) {

                for(int i=; i<str.length(); ++i) {

                    for(char ch = 'a'; ch <= 'z'; ++ch) {

                        if(str[i] != ch) {

                            string tmp = str;

                            tmp[i] = ch;

                            if(wordList.find(tmp) != wordList.end() && vis.find(tmp) == vis.end()) {

                                next_lev.insert(tmp);

                                fa[tmp].push_back(str);

                            }

                        }

                    }

                }

            }

            lev.clear();

            swap(lev, next_lev);

        }

        if(found) {

            vector<string> load;

            load.push_back(endWord);

            dfs(res, fa, load, beginWord, endWord);

        }

        return res;

    }

};