C++ Output Limit Exceeded 'error'


  • 0

    I use BFS to find the paths, and then use DFS to construct the results.
    However, it gives me the "Output Limit Exceeded" error for the following case:

    "charge"
    "comedo"
    ["shanny","shinny",...,"salton"]

    I assume that the code is correct for previous cases. Can anybody help me analyse why it fails for this one?
    Thanks very much!!!

    class Solution {
    public:
    void dfs(vector<vector<string>> &res, vector<string> & post, string & endWord, unordered_map<string,vector<string>> & tree){
        string temp=post.back();
        if (temp==endWord) {
            res.push_back(post);
            return;
        }
        for (int i=0;i<tree[temp].size();i++){
            post.push_back(tree[temp][i]);
            dfs(res,post,endWord,tree);
            post.pop_back();
        }
    }
    
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
        vector<vector<string>> res;
        int len = beginWord.size();
        unordered_map<string,vector<string>> tree;
        vector<string> noneset;
        tree[endWord]=noneset;
        queue<string> preLayer;
        preLayer.push(endWord);
        int flag = 1;
        while (!preLayer.empty() && flag){
            int k = preLayer.size();
            for (int m=0;m<k;m++){
                wordList.erase(preLayer.front());
                preLayer.push(preLayer.front());
                preLayer.pop();
            }
            for (int m=0;m<k;m++){
                string cur=preLayer.front();
                preLayer.pop();
                for (int i=0;i<len;i++){
                    string temp=cur;
                    for (temp[i]='a';temp[i]<'z';temp[i]++){
                        if (temp==beginWord){
                            flag=0;
                        }
                        if (wordList.find(temp)!=wordList.end()){
                            preLayer.push(temp);
                            if (tree.find(temp)!=tree.end()){
                                tree[temp].push_back(cur);
                            }else{
                                vector<string> source;
                                source.push_back(cur);
                                tree[temp]=source;
                            }
                        }
                    }
                }
            }
        }
        if (flag) return res;
        vector <string> post;
        post.push_back(beginWord);
        dfs(res,post,endWord,tree);
        return res;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.