Accepted cpp solution without memory leak


  • 0
    T
    const int ALPHA_SIZE = 'z'-'a'+1;
    class TrieNode {
    public:
    	// Initialize your data structure here.
    	TrieNode *childs[ALPHA_SIZE];
    	bool isWordTail;
    	TrieNode():isWordTail(false){
            memset(childs, 0, sizeof(childs));
    	}
    	~TrieNode(){
    		for (int i = 0; i < ALPHA_SIZE; ++i)
    		{
    			if (childs[i] != NULL)
    			{
    				delete childs[i];
    				childs[i] = NULL;
    			}
    		}
    	}
    };
    
    class Trie {
    public:
    	Trie() {
    		root = new TrieNode();
    	}
    	~Trie(){
    		delete root;
    		root = NULL;
    	}
    
    	// Inserts a word into the trie.
    	void insert(string s) {
    	    const int N = s.length();
    		TrieNode* curpar = root;
    		for (int i = 0; i < N; ++i)
    		 {
    			 int curidx = s[i] - 'a';
    			 if (curpar->childs[curidx] == NULL)
    			 {
    				 curpar->childs[curidx] = new TrieNode();
    			 }
    			 curpar = curpar->childs[curidx];
    		 }
    		curpar->isWordTail = true;
    	}
    
    	// Returns if the word is in the trie.
    	bool search(string key) {
    	    const int N = key.length();
    		if (N == 0) return false;
    		TrieNode* curpar = root;
    		for (int i = 0; i < N; ++i)
    		{
    			curpar = curpar->childs[key[i] - 'a'];
    			if (curpar == NULL)	return false;
    		}
    		return curpar->isWordTail;
    	}
    
    	// Returns if there is any word in the trie
    	// that starts with the given prefix.
    	bool startsWith(string prefix) {
    	    const int N = prefix.length();
    		if (N == 0)  return false;
    		TrieNode* curpar = root;
    		for (int i = 0; i < N; ++i)
    		{
    			curpar = curpar->childs[prefix[i] - 'a'];
    			if (curpar == NULL)	return false;
    		}
    		return true;
    	}
    
    private:
    	TrieNode* root;
    };

Log in to reply
 

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