DFS and Trie


  • 0
    N

    Trie + DFS

    Time Complexity:
    addWord O(len(word))
    search O(26 ^ len(word))

    Submission Runtime 145ms

    Make use of lc208 Implement Trie. First define a TrieNode struct, is_word is very important to indicate current node is end the of a word or not.

        struct TrieNode {
            bool is_word;
            TrieNode* children[26];
            TrieNode (bool word=false) {
                memset(children, 0, sizeof(children));
                is_word = word;
            }
        };
    
    
    
    WordDictionary() {
         root = new TrieNode();
    }
    

    addWord is as same as lc208

    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode* node = root;
        for (int i = 0; i < word.size(); i++) {
            if (node->children[word[i] - 'a'] == nullptr) {
                node->children[word[i] - 'a'] = new TrieNode();
            }
            node = node->children[word[i] - 'a'];
        }
        
        node->is_word = true;
    }
    

    the trivial part is how to deal with '.' . This indicates we should explore all possibilities when running into a '.'. Here DFS + backtracking saves the day.

    The recursion function defines whether we can find substring word[pos, last] in node-rooted subtree.

    /** 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 find(word, 0, root);
    }
    
    bool find(string word, int pos, TrieNode* node) {
        if (pos == word.size()) {
            return node->is_word;
        }
        
        if (word[pos] != '.') {
            if (node->children[word[pos] - 'a']) {
                return find(word, pos + 1, node->children[word[pos] - 'a']);
            } 
        } else {
            for (int i = 0; i < 26; i++) {
                if (node->children[i] != nullptr &&
                    find(word, pos + 1, node->children[i]))
                    return true;
            }
        }
        
        return false;
    }
    

    One of my question is why my solution is so slow. I think time complexity is just like what I mentioned before when using trie. Anyone can point out optimization . Thanks a lot


Log in to reply
 

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