share my different Trie structure


  • 0
    Z
    struct Trie {
        Trie *map[27];
        Trie() {memset(map, NULL, sizeof(map));}
    };
    
    class WordDictionary {
    public:
        /** Initialize your data structure here. */
        WordDictionary() {
            root = new Trie();
        }
        
        /** Adds a word into the data structure. */
        void addWord(string word) {
            Trie *p = root;
            for (char c : word) {
                if (!p->map[c - 'a']) p->map[c - 'a'] = new Trie();
                p = p->map[c - 'a'];
            }
            p->map[26] = (Trie *)new bool;
        }
        
        /** 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) {
            Trie *p = root;
            return dfs(word, 0, word.size(), p);
        }
    private:
        Trie *root;
        
        bool dfs(string &word, int pos, int size, Trie *p) {
            if (pos == size) return p->map[26] != NULL;
            if (word[pos] == '.') {
                for (int i = 0; i < 26; ++i)
                    if (p->map[i] && dfs(word, pos + 1, size, p->map[i])) 
                        return true;
            } else return p->map[word[pos] - 'a'] && dfs(word, pos + 1, size, p->map[word[pos] - 'a']);
            return false;
        }
    };
    

Log in to reply
 

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