每日leetcode-126

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

输出:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
  [“hit”,”hot”,”lot”,”log”,”cog”]
]
示例 2:

输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

输出: []

解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

一个简单的BFS。

每一轮检查上一轮的时候加进去的单词的相邻单词，发现没有检查过的就加进去。

直接用两个变量存储每一轮加进去的点和剩下的单词。

class Solution {
public:
    bool is_change_one(const string& a, const string& b) {
        int lena = a.size();
        int diff = 0;
        for (int i = 0; i < lena; i++) {
            if (a[i] != b[i]) {
                diff += 1;
            }
        }
        return diff == 1;
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int all_size = wordList.size();  // wordList
        map<string, vector<vector<string>>> shortest_record;
        vector<vector<string>> temp;
        vector<string> t2;
        t2.push_back(beginWord);
        temp.push_back(t2);
        shortest_record[beginWord] = temp;

        // start node
        set<string> available;  // 没有处理的
        set<string> lasttime; // 上次的单词
        lasttime.insert(beginWord);
        bool end_in = false;
        for (auto i = wordList.begin(); i != wordList.end(); i++) {
            available.insert(*i);
            if (*i == endWord) {
                end_in = true;
            }
        }
        
        if (!end_in) {
            return vector<vector<string>>();
        }

        while (!lasttime.empty()) {
            bool got_ans = false;
//            cout << "\nLasttime: ";
//            for (auto tt = lasttime.begin(); tt != lasttime.end(); tt++) {
//                cout << " " << *tt;
//            }
//            cout << "\nAva: ";
//            for (auto tt = available.begin(); tt != available.end(); tt++) {
//                cout << " " << *tt;
//            }
//            cout << "\n======";
            vector<vector<string>> result;
            for (auto cand = lasttime.begin(); cand != lasttime.end(); cand++) {
                if (is_change_one(*cand, endWord)) {
                    got_ans = true;
                    vector<vector<string>> &a = shortest_record[*cand];
                    for (auto ttt = a.begin(); ttt != a.end(); ttt++) {
                        result.push_back(vector<string>(*ttt));
                        (*(result.end() - 1)).push_back(endWord);
                    }
                }
            }
            if (got_ans) {
                return result;
            }
            set<string> new_lasttime;
            set<string> new_available;
            for (auto now = available.begin(); now != available.end(); now++) {
                bool got_ans = false;
                vector<vector<string>> result;
                for (auto cand = lasttime.begin(); cand != lasttime.end(); cand++) {
                    if (is_change_one(*cand, *now)) {
                        got_ans = true;
                        vector<vector<string>> &a = shortest_record[*cand];
                        for (auto ttt = a.begin(); ttt != a.end(); ttt++) {
                            result.push_back(vector<string>(*ttt));
                            (*(result.end() - 1)).push_back(*now);
                        }
                    }
                }
                if (got_ans) {
                    shortest_record[*now] = result;
                    new_lasttime.insert(*now);
                }
                else {
                    new_available.insert(*now);
                }
            }
            available = move(new_available);
            lasttime = move(new_lasttime);
        }
        return vector<vector<string>>();
    }
};

但是用了一秒多。

24ms的示例代码

class Solution {
public:
    vector<vector<string>> res;
    unordered_map<string, vector<string>> hash;
    
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dirc(wordList.begin(), wordList.end());
        if (dirc.find(endWord) == dirc.end()) return res;
        unordered_set<string> beginw{beginWord};
        unordered_set<string> endw{endWord};
        int flag1 = 0, flag2 = 0;  //第一个是否找到最短序列标志, 第二个是否反转标志。
        
        while (!beginw.empty()) {
            unordered_set<string> tmp;
            for (auto str : beginw) dirc.erase(str);
            for (auto str : beginw) { //每次都是对beginw进行操作，所以后面有判断让beginw比endw小
                for (int i = 0; i < str.size(); ++i) {
                    string s = str;
                    for (char j = 'a'; j <= 'z'; ++j) {
                        s[i] = j;
                        if (dirc.find(s) == dirc.end()) continue;  // 在候选里面没有现在判断的这个可能的下一个
                        if (endw.find(s) != endw.end()) flag1 = 1;// 已经到头了
                        else tmp.insert(s);// 接下来就是从这个开始进行搜索
                        flag2 ? hash[s].push_back(str) : hash[str].push_back(s);// 记录一下前后关系  // 刚开始flag2是0，所以刚开始的时候是把s记录在str的里面
                    } 
                }
            }
            if (flag1) break;  //已经找到最短序列退出循环。
            if (tmp.size() <= endw.size()) // 判断让beginw比endw小
                beginw = tmp;
            else {
                beginw = endw; endw = tmp; 
                flag2 = !flag2;  //这里需要使用！反转。
            }
        }
        vector<string> ans = {beginWord};
        dfs(ans, beginWord, endWord);
        return res;
    }
    
    void dfs(vector<string>& ans, string& begin, string& end) {
        if (begin == end) {
            res.emplace_back(ans);
            return;
        }
        if (hash.find(begin) == hash.end()) return;
        for (auto str : hash[begin]) {
            ans.emplace_back(str);
            dfs(ans, str, end);
            ans.pop_back();
        }
    }
};

1. 用了unordered_set而不是set，区别可以见https://cloud.tencent.com/developer/article/1338333，性能上差的还是挺多的
2. 构造函数可以直接用unordered_set dirc(wordList.begin(), wordList.end());，不必写个for循环来整；
3. 两个方向进行操作，让比较少的一头开始；
4. unordered_set进行find操作是很快的
5. 记录的时候没有必要记录到这个节点的全部路径，只用记录下来从上一个节点的路径就可以了，最后用一个深搜就行（因为现在最多的能连上的层数就是最短的，不会有更长的能连起来的）