How to optimize this code?


  • 0
    O

    How can I optimize the code to get a faster running time? I've submit it several times and and always above 200ms, I've check several faster code but the algorithm applied is similar, which is the bottleneck in this code?

    class WordDictionary {
    public:
    
    	struct Dict {
    		vector<Dict*> next;
    		bool finish;
    		Dict() : finish(false) {
    			for(int i = 0; i < 26; i++)
    				next.push_back(NULL);
    		}
    	};
    
    	Dict dt;
    
    	// Adds a word into the data structure.
    	void addWord(string word) {
    		Dict* nx = &dt;
    		for(int i = 0; i < word.size(); i++){
    			int n = word[i] - 'a';
    			if(nx -> next[n] == NULL) nx -> next[n] = new Dict();
    			nx = nx -> next[n];
    		}		
    		nx -> finish = true;
    	}
    
    	// Returns if the word is in the data structure. A word could
    	// contain the dot character '.' to represent any one letter.
    	bool search(string word) {
    		return sub_search(word, &dt);
    	}
    
    	bool sub_search(string word, Dict* dir){
    		for(int i = 0; i < word.size(); i++){
    			if(word[i] == '.'){
    				for(int j = 0; j < 26; j++){
    					if(dir -> next[j] && sub_search(word.substr(i + 1, word.size() - i - 1), dir -> next[j]))
    						return true;
    				}
    				return false;
    			}
    			else{
    				int n = word[i] - 'a';
    				if(dir -> next[n] == NULL) return false;
    				dir = dir -> next[n];
    			}
    		}
    		return dir -> finish;
    	}
    };

  • 1
    R

    Hi, ohbrown

    Change one line of your code to

    Dict* next[26];
    

    You will find your code is as fast as others.
    Because when you initial each node, the push_back operation will cost some time, which is considerable for all the nodes. But an array is light-weighted in this problem.


  • 0
    O

    Yeah! That is indeed the bottleneck, and I've got a 96ms solution after the code changed!! Thank you!


Log in to reply
 

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