C++ Trie solution && works well


  • 0
    X
    class WordDictionary {
    public:
        struct TreeNode{
        	char c;
        	bool isWord;
        	TreeNode* child[26];
        
        	TreeNode(){
        		c = 0;
        		isWord = false;
        		memset(child, 0x0, sizeof(TreeNode*)* 26);
        	}
        	TreeNode(char val){
        		c = val;
        		isWord = false;
        		memset(child, 0x0, sizeof(TreeNode*)* 26);
        	}
        };
    private:
    	TreeNode* root;
    	bool helper(int index, string& word, TreeNode* pNow){
    		int idx;
    		if (index == word.size() - 1){
    			if (word[index] != '.'){
    				idx = word[index] - 'a';
    				if (pNow->child[idx] != NULL&&pNow->child[idx]->isWord)
    					return true;
    				else
    					return false;
    			}
    			else{
    				for (idx = 0; idx<26; idx++){
    					if (pNow->child[idx] != NULL&&pNow->child[idx]->isWord)
    						return true;
    				}
    				return false;
    			}
    		}
    		else{
    			if (word[index] != '.'){
    				idx = word[index] - 'a';
    				if (pNow->child[idx] != NULL)
    					return helper(index + 1, word, pNow->child[idx]);
    				else
    					return false;
    			}
    			else{
    				for (idx = 0; idx<26; idx++){
    					if (pNow->child[idx] && helper(index + 1, word, pNow->child[idx]))
    						return true;
    				}
    				return false;
    			}
    		}
    	}
    public:
    	WordDictionary(){
    		root = new TreeNode();
    	}
    	// Adds a word into the data structure.
    	void addWord(string word) {
    		if (word.size() <= 0)  return;
    		TreeNode* pNow = root;
    		for (int i = 0; i<word.size(); i++)
    		{
    			int idx = word[i] - 'a';
    			if (pNow->child[idx] == NULL){
    				TreeNode* tmp = new TreeNode(word[i]);
    				pNow->child[idx] = tmp;
    				pNow = pNow->child[idx];
    			}else{
    			    pNow = pNow->child[idx];
    			}
    		}
    		pNow->isWord = 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) {
    		if (word.size() <= 0)  return false;
    		TreeNode* pNow = root;
    		return helper(0, word, pNow);
    	}
    
    };

Log in to reply
 

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