Help with improving performance


  • 0
    V
    class Solution {
    public:
        bool is_a_solution(int k,string endWord,vector<string> res){
            
            return ((k > 0) && (res[k-1] == endWord));
        }
        
        void process_solution(vector<string> res, vector<vector<string>> &result){
            result.push_back(res);
        }
        
        void construct_candidates(int k,queue<string> &candidates,vector<string> res,unordered_set<string>& wordSet, string beginWord){
            if(k == 0){
                candidates.push(beginWord);
            }
            else{
                if(wordSet.empty())
                    return;
                string val = res[k-1];
                int i = 0;
                for(auto ch:val){
                    char temp = ch;
                    for(char j ='a';j<='z';j++){
                        val[i] = j;
                        if(wordSet.find(val) != wordSet.end()){
                            candidates.push(val);
                            wordSet.erase(val);
                        }
                    }
                    val[i] = temp;
                    i++;
                }
            }
        }
        void backtrack(int k,string beginWord,string endWord,unordered_set<string> wordSet,vector<string>& res,vector<vector<string>> &result){
            queue<string> candidates;
            if(is_a_solution(k,endWord,res)){
                process_solution(res,result);
            }
            else{
                construct_candidates(k,candidates,res,wordSet,beginWord);
                while(!candidates.empty()){
                    res.push_back(candidates.front());
                    candidates.pop();
                    backtrack(k+1,beginWord,endWord,wordSet,res,result);
                    res.pop_back();
                }
            }
        }
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            if(wordList.size() == 0)
                return vector<vector<string>>();
            
            vector<vector<string>> result;
            vector<string> res;
            unordered_set<string> wordSet(wordList.begin(),wordList.end());
            backtrack(0,beginWord,endWord,wordSet,res,result);
            return result;
        }
    };
    

    My code gives time limit exceeded. This is probably an inefficient solution. I would appreciate any help in understanding the time consuming areas and how to improve it. The idea behind this is that I am trying to follow the template given in Algorithm Design Manual and would love to keep a constant template for my backtracking solutions.


  • 0
    F

    @vick4523zf I haven't studied your code for too long, but it seems that in construct_candidates you have nested loops where do generate all possible words and constantly testing which ones are in the dictionary. First, we know that all words have the same length, so it is useless to check when your partial word has a smaller length.But most importantly I believe your "backtrack" solution is equivalent to a brute force. From what I know, the backtrack approach benefit is that it can eliminates candidates that cannot become a solution. But in this problem, one can't tell if a word will or will not turn into a solution later.

    The usual solution is to generate a graph where each node is a word, and two nodes are connected if they have only one letter that differs. Using such graph you don't need to inspect each possible "word" (and there can be a whole lot if you try every letter at every position). Looking at these nodes only reduces the space considerably, and then it's about finding the shortest path between two nodes.


Log in to reply
 

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