211. Add and Search Word - Data structure design

Problem description:

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Solution:

Most of the part is similar to 208. Implement Trie (Prefix Tree). The only thing we need to modify is the search part.

Since we now have '.' to check, we can use DFS to check whether if the trie tree contains the string after the '.'. If there’s at least one subtree return true, that means we can find a word in trie.

Another follow up for this question is adding '*'

class TrieNode:
    def __init__(self):
        self.end = False
        self.child = defaultdict(TrieNode)
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
        
    def addWord(self, word: str) -> None:
        p = self.root
        for c in word:
            p = p.child[c]
        p.end = True

    def search(self, word: str) -> bool:
        node = self.root
        self.res = False
        self.dfs(node, word, 0)
        return self.res

    def dfs(self, node, word, i):
        if i == len(word):
            if node.end:
                self.res = True
            return
        if word[i] == '.':
            for n in node.child.values():
                self.dfs(n, word, i + 1)
        elif word[i] == '*':
            if i+1 == len(word): return True # last character, * can be treat as empty
            if dfs(word, node, i+1): return True # skip it
            for n in node.child.values():
                if (word[i+1] in n.child or word[i+1] == '.' or word[i+1] == '*') and dfs(word, n, i+1):
                    return True
                if dfs(word, n, i): return True
            return False
        else:
            node = node.child.get(word[i])
            if not node:
                return
            self.dfs(node, word, i + 1)

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

//design a TrieNode class
class TrieNode{
public:
    TrieNode* child[26];
    bool isWord;
    TrieNode(): isWord(false){
        for(auto &c: child)
            c= NULL;
    }
};

class WordDictionary {
public:
    TrieNode* root; //global variable root
    
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode* tmp= root;
        for(auto c: word){
            int i= c- 'a';
            if(!tmp->child[i]) 
                tmp->child[i]= new TrieNode();
            
            tmp = tmp->child[i];
        }
        tmp->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) {
        //need to consider the '.'
        //follow up: '*'
        return searchWord(word, root, 0);
    }
    
    bool searchWord(string &word, TrieNode *p, int i) {
        if(i == word.length()) return p->isWord;
        if(word[i] == '.'){
            for(auto c: p->child){
                //DFS, if child c is existed and we can find next character in trie, return true
                if(c && searchWord(word, c, i+1)) return true; 
            }
            return false; 
        }
        /* follow up for '*'
        else if (word[i] == '*') {
            if (i + 1 == word.size()) return true; //this * is the last character, * can treat as empty
            if (searchWord(word, p, i + 1)) return true; // Skip *
            for (auto &a : p->child) {
                if (a && (a->child[word[i + 1] - 'a'] || word[i + 1] == '.' || word[i + 1] == '*') && searchWord(word, a, i + 1)) return true;
                if (a && searchWord(word, a, i)) return true;
            }
            return false;
        */
        
        else{
            int index= word[i]- 'a';
            return p->child[index] && searchWord(word, p->child[index], i+1);
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * bool param_2 = obj.search(word);
 */

addWord:
time complexity: $O(l)$, l is the average length of word
space complexity: $O(l)$

search:
time complexity: $O(26^l)$, l is the average length of word
space complexity: $O(1)$

Overall space Complexity - $O(26^l)$, l is the average length of word

reference:
https://goo.gl/2AQFjo
https://goo.gl/pihuH1