纯BFS做法，缺点是空间复杂度较高，但仍然beat了100 %的人

思路：
创建一个队列paths，当其不为空的时候，每次弹出元素path。定义level表示层次大小，以及minlevel表示最短路长度。 当到达新的level的时候，把上一层的元素从word中全部删删除。之后开始bfs，把每个单词的新路径放入newpath，如果找到了答案就储存。

参考自leetcode国际版

class Solution {
public: 
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> ans;
        queue<vector<string>> paths;               
        unordered_set<string> word{wordList.begin(), wordList.end()};
        paths.push({beginWord});
        int level = 1;
        int minLevel = INT_MAX;

        unordered_set<string> visited;             // 记录在本层访问过的词。

        while (!paths.empty()) {
            vector<string> path = paths.front();
            paths.pop();
            if (path.size() > level) {
                //reach a new level
                for (string w : visited) word.erase(w);      // 删除所有已访问过的词
                visited.clear();
                if (path.size() > minLevel)                  // 当minlevel第一次被访问到的时候，自动更新为最小值
                    break;
                else
                    level = path.size();
            }
            string last = path.back();

            for (int i = 0; i < last.size(); ++i) {
                string news = last;
                for (char c = 'a'; c <= 'z'; ++c) {
                    news[i] = c;
                    if (word.find(news) != word.end()) {

                        vector<string> newpath = path;
                        newpath.push_back(news);
                        visited.insert(news);
                        if (news == endWord) {
                            minLevel = level;
                            ans.push_back(newpath);      
                        }
                        else
                            paths.push(newpath);
                    }
                }
            }
        }
        return ans;
    }
};