[Rainbow] template refered to jianchao.li.fighter


  • 0
    2

    faced this problem , almost all the code is just rewrite the original Tie implementation.

    The difficulty lays that how we deal with the '.'

    class TrieNode {
    public: 
        bool isWord;
        TrieNode* children[26];
        TrieNode() : isWord(false) {
            memset(children, 0, sizeof(children));
        }
    };
    
    class WordDictionary {
        TrieNode* root;
    
    public:
        WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode* cur = root;
            for(char c : word) {
                if(!cur->children[c-'a']) {
                    cur->children[c-'a'] = new TrieNode();
                }
                cur = cur->children[c-'a'];
            }
            cur->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) {
            return query(word.c_str(), root);
        }
        
        /** the key is to implement this support '.' function **/
        bool query(const char* word, TrieNode* node) {
            TrieNode* cur = node;
            for(int i = 0; word[i]; i++) {
                if(cur && word[i] != '.') {
                    cur = cur->children[word[i]-'a'];
                }
                else if(cur && word[i] == '.') {
                    TrieNode* temp = cur;
                    for(int j = 0; j < 26; j++) {
                        cur = temp->children[j];
                        if(query(word + i + 1, cur)) {
                            return true;
                        }
                    }
                }
                else {
                    break;
                }
            }
            return cur && cur->isWord;
        }
    };

Log in to reply
 

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