求助|LC126我的解法,最快也就8ms,请问如何改进?求大佬指点

77
2026.11.16
2026.11.16
发布于 江苏
PlainText
class Solution {
    struct kidnodeinfo{
        int distance = 1412;
        vector<int> all_source_nodes = vector<int>();

        kidnodeinfo(){}
        kidnodeinfo(int d, vector<int> v):distance(d),all_source_nodes(v){}
    };
    
    vector<vector<string>> result;
    vector<string> templadder;
    void getting_ladders(const kidnodeinfo*, const vector<string>&, const int&);
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        const int listlen = wordList.size();
        //建立通配符字典,便于查看某个词的所有相邻词
        unordered_map<string, vector<int>> worddict;
        kidnodeinfo kidconnection[1412];//邻接表节点

        int endlabel = -1, beginlabel = -1;
        for(int wordlabel = 0; wordlabel < listlen; wordlabel++){
            string& word = wordList[wordlabel];
            endlabel = (word==endWord ? wordlabel : endlabel);
            beginlabel = (word==beginWord ? wordlabel : beginlabel);
            kidconnection[wordlabel]= kidnodeinfo();//顺手初始化邻接表节点
            for(char& c:word){
                char originc = c;
                c = '*';
                if(worddict.find(word)==worddict.end())worddict[word] = vector<int>();
                vector<int>& targetdict = worddict[word];
                c = originc;
                targetdict.push_back(wordlabel);
            }
        }

        if(endlabel==-1)return result;
        else kidconnection[endlabel] = kidnodeinfo(0, {endlabel});

        bool pushed = false;
        if(beginlabel == -1){
            pushed = true;
            beginlabel = listlen;
            wordList.push_back(beginWord);
            kidconnection[listlen] = kidnodeinfo();
            for(char& c:beginWord){
                char originc = c;
                c = '*';
                if(worddict.find(beginWord)==worddict.end())worddict[beginWord] = vector<int>();
                vector<int>& targetdict = worddict[beginWord];
                c = originc;
                targetdict.push_back(listlen);
            }
        }

        //邻接表各个节点已经顺手初始化,接下来直接更新邻接表节点
        vector<int> scannode = {endlabel}, nextscan = {};
        while(!scannode.empty()){
            //扫描本次要更新的节点
            for(const int& scanlabel:scannode){
                string& scan = wordList[scanlabel];
                //遍历该节点的所有通配符
                for(char& c:scan){
                    char originc = c;
                    c = '*';
                    //该通配符下所有节点就是与其相邻的节点,注意除掉它自己
                    const vector<int>& adjacent_labels = worddict[scan];
                    c = originc;
                    const kidnodeinfo& scaninfo = kidconnection[scanlabel];
                    for(const int& ad_label:adjacent_labels){
                        kidnodeinfo& nextinfo = kidconnection[ad_label];
                        if(nextinfo.distance == 1412){
                            nextinfo.distance = scaninfo.distance+1;
                            nextscan.push_back(ad_label);
                            nextinfo.all_source_nodes.push_back(scanlabel);
                        }
                        else if(nextinfo.distance == scaninfo.distance+1){
                            nextinfo.all_source_nodes.push_back(scanlabel);
                        }
                    }
                }
            }

            swap(scannode, nextscan);
            nextscan.clear();
        }
        
        //获取所有路径
        getting_ladders(kidconnection, wordList, beginlabel);

        if(pushed)wordList.pop_back();

        return result;
    }
};

void Solution::getting_ladders(const kidnodeinfo* connection, const vector<string>& wordlist, const int& nowlabel){
    templadder.push_back(wordlist[nowlabel]);
    if(connection[nowlabel].distance == 0){
        result.push_back(templadder);
    }
    else{
        for(const int& nextnode:connection[nowlabel].all_source_nodes){
            getting_ladders(connection, wordlist, nextnode);
        }
    }
    templadder.pop_back();
}

评论 (0)