Clear and easy c++ solution


  • 2
    V
    class TrieNode {
    public:
    	TrieNode *next[26] = {NULL};
    	bool isend = false;
    	TrieNode() {
    		
    	}
    };
    class WordDictionary {
    public:
    	TrieNode *root;
    	WordDictionary() {
    		root = new TrieNode();
    	}
    	void addWord(string word) {
    		TrieNode *p = root;
    		for (int i = 0; i < word.size(); i++) {
    			if (p->next[word[i] - 'a'] == NULL)
    				p->next[word[i] - 'a'] = new TrieNode();
    			p = p->next[word[i] - 'a'];
    		}
    		p->isend = true;
    	}
    	bool search(string word) {
    		return help(word, root);
    	}
    	bool help(string word, TrieNode *root) {
    		TrieNode *p = root;
    		for (int i = 0; i < word.size(); i++) {
    			if (word[i] != '.') {
    				if (p->next[word[i] - 'a'] == NULL)
    					return false;
    				p = p->next[word[i] - 'a'];
    			}
    			else {
    				TrieNode *q = p;
    				for (int j = 0; j < 26; j++) {
    					if (q->next[j] != NULL && help(word.substr(i + 1), q->next[j]))
    						return true;
    				}
    				return false;
    			}
    		}
    		return p->isend;
    	}
    };

  • 0
    T

    class TrieNode {
    public:
    // Initialize your data structure here.
    TrieNode* next[26]; //指向各个子树的指针
    bool exist; //标记该节点处是否构成单词
    TrieNode() {
    exist = false;
    memset(next, 0, 26 * sizeof(TrieNode *));
    }
    };

    class WordDictionary {
    public:
    WordDictionary() {
    root = new TrieNode();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* node = root;
        int index;
        for (int i = 0; i < word.length(); i++){
            index = word[i] - 'a';
            if (node->next[index] == NULL)
                node->next[index] = new TrieNode; 
            node = node->next[index];
        }
        node->exist = true;
    }
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(TrieNode* root, string word) {
        if (root == NULL)
        {
            return false;
        }
        if (word.size() == 0)
        {
            return root->exist; 
        }
        if (word[0] == '.')
        {
            for (int i = 0; i < 26; i++)
            { 
                if(search(root->next[i], word.substr(1)))
                {
                    return true;
                }
            }
            return false;
        }
        int index = word[0] - 'a';
        return search(root->next[index], word.substr(1));
    }
    
    bool search(string word)
    {
        return search(root, word);
    }
    
    private:
    TrieNode* root;
    

    };

    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary;
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");


Log in to reply
 

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