126. 单词接龙 II

给定两个单词（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”]
]
https://blog.csdn.net/Bendaai/article/details/80951542
https://blog.csdn.net/qq_17550379/article/details/83652490
我的代码 超时

static int y=[]()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
vector<vector<int>> v_e;
vector<vector<string>> v_solution;
vector<int> x;
string bWord;
string eWord;
int n;
int min_len;
int compare(string endWord,string wordLi)
{
    int num=0;
    for(int i=0;i<endWord.length();i++)
    {
        if(endWord[i]!=wordLi[i])
            num++;
    }
    return num;
}
bool isok(string nWord,vector<string>& words)
{
    for(int i=0;i<x.size();i++)
        if(nWord==words[x[i]]) return false;
    if(nWord==bWord) return false;
    return true;
}
void dfs(int t,string nowWord,vector<string>& words,int len)
{
    if(len+t>min_len) return;
    if(t==0)
    {
        if(min_len>len)
            min_len=len;
        vector<string> temp;
        temp.push_back(bWord);
        for(int i=0;i<x.size();i++)
            temp.push_back(words[x[i]]);
        v_solution.push_back(temp);
        return ;
    }
    else
    {
        for(int i=0;i<v_e[t-1].size();i++)
        {
            if(compare(nowWord,words[v_e[t-1][i]])==1)
            {
                x.push_back(v_e[t-1][i]);
                dfs(t-1,words[v_e[t-1][i]],words,len+1);
                x.pop_back();
            }
            
        }
        if(min_len==n+1) return;
        if(len+t+1>min_len) return;
            for(int i=0;i<v_e[t].size();i++)
            {
                 if(compare(nowWord,words[v_e[t][i]])==1&&isok(words[v_e[t][i]],words))
                 {
                       x.push_back(v_e[t][i]);
                       dfs(t,words[v_e[t][i]],words,len+1);
                       x.pop_back();
                 }
            }
    }
    return;
}
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        bWord=beginWord;
        min_len=wordList.size();
        eWord=endWord;
        int len=beginWord.size();
        n=compare(endWord,beginWord);
        vector<vector<string>>().swap(v_solution);
        vector<int>().swap(x);
        vector<vector<int>>().swap(v_e); 
        v_e.resize(len+1);
        vector<vector<string>> v_find;
        for(int i=0;i<wordList.size();i++)
        {
            int e=compare(endWord,wordList[i]);
            v_e[e].push_back(i);
        }
        if(v_e[0].size()==0) return v_solution;
        dfs(n,beginWord,wordList,1);
        for(int i=0;i<v_solution.size();i++)
        {
           if(v_solution[i].size()==min_len)
                v_find.push_back(v_solution[i]);
        }
        return v_find;
    }
};

最短代码 820 ms 178.6 MB

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        vector<string> p{beginWord};
        queue<vector<string>> paths;
        paths.push(p);
        int level = 1, minLevel = INT_MAX;
        unordered_set<string> words;
        while (!paths.empty()) 
        {
            auto t = paths.front(); paths.pop();
            if (t.size() > level) 
            {
                for (string w : words) dict.erase(w);
                words.clear();
                level = t.size();
                if (level > minLevel) break;
            }
            string last = t.back();
            for (int i = 0; i < last.size(); ++i) 
            {
                string newLast = last;
                for (char ch = 'a'; ch <= 'z'; ++ch) 
                {
                    newLast[i] = ch;
                    if (!dict.count(newLast)) continue;
                    words.insert(newLast);
                    vector<string> nextPath = t;
                    nextPath.push_back(newLast);
                    if (newLast == endWord) 
                    {
                        res.push_back(nextPath);
                        minLevel = level;
                    } else paths.push(nextPath);
                }
            }
        }
        return res;
    }
};

最快代码 48 ms 17.4 MB

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int N = beginWord.size();
        vector<vector<string>> ret;
        wordList.push_back(beginWord);
        vector<unordered_set<int>> link(wordList.size());
        unordered_map<string, int> word2id;
        for (int i = 0; i < wordList.size(); ++i){
            word2id[wordList[i]] = i;
        }
        if (word2id.count(endWord) == 0) return ret;
        int startId = wordList.size() - 1;
        int endId = word2id[endWord];

        vector<bool> visited(wordList.size(), false);
        unordered_set<int> a, b;
        a.insert(startId);
        b.insert(endId);
        visited[startId] = true;
        visited[endId] = true;
        while (!a.empty() && !b.empty() && ret.empty()){
            unordered_set<int> tmp;
            if (a.size() > b.size()){
                swap(a, b);
            }
            for (int x : a){
                string w = wordList[x];
                for (int i = 0; i < N; ++i){
                    char t = w[i];
                    for (char c = 'a'; c <= 'z'; ++c){
                        w[i] = c;
                        auto it = word2id.find(w);
                        if (t == c || it == word2id.end()) continue;
                        if (b.count(it->second)){
                            build(x, it->second, link, wordList, ret);
                        }
                        else if (!visited[it->second]){
                            tmp.insert(it->second);
                            link[it->second].insert(x);
                        }
                    }
                    w[i] = t;
                }
            }
            for (int i : tmp){
                visited[i] = true;
            }
            swap(tmp, a);
        }
        return ret;
    }

    void build(int x, int y, vector<unordered_set<int>>& link, vector<string>& wordList, vector<vector<string>>& ret){
        vector<vector<int>> left, right;
        vector<int> vec = { x };
        dfs(vec, link, left);
        vec[0] = y;
        dfs(vec, link, right);
        for (auto& v1 : left){
            for (auto& v2 : right){
                ret.push_back({});
                vector<string>& r = ret.back();
                for (int i = v1.size() - 1; i >= 0; --i){
                    r.push_back(wordList[v1[i]]);
                }
                for (int i = 0; i < v2.size(); ++i){
                    r.push_back(wordList[v2[i]]);
                }
                if (v1.back() != wordList.size() - 1){
                    reverse(r.begin(), r.end());
                }
            }
        }
    }
    void dfs(vector<int>& vec, vector<unordered_set<int>>& link, vector<vector<int>>& ret){
        int i = vec.back();
        if (link[i].empty()){
            ret.push_back(vec);
        }
        else{
            for (int j : link[i]){
                vec.push_back(j);
                dfs(vec, link, ret);
                vec.pop_back();
            }
        }
    }
};