leetcode Question: Add and Search Word - Data structure design

Add and Search Word - Data structure design

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.

For 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.

Analysis:

This is quite similar to the previous question  Implement Trie (Prefix Tree), where a Trie data structure is required to be implemented.

The only difference in this question is to add a DFS search (or back tracking). The figure below shows the general idea of this question.  Implement details is much similar to "Implement Trie (Prefix Tree)".  When you do search, be careful with the few lines of code related to backtracking. Note that, it is not "return search(...)", but you have to check every child of current node, if there is one True return, the result is True.

Code(C++):

class TrieNode {
public:
    TrieNode(){
        value = 0;
        for (int i=0;i<26;i++){
            children[i]=NULL;
        }
    }
    int value;
    TrieNode* children[26];
};


class WordDictionary {
private:
    TrieNode* trie;
    int count;
public:

    // Constructor
    WordDictionary(){
        trie = new TrieNode();
        count  = 0;
    }
    
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* p = trie;
        int l = word.size();
        for (int i=0;i<l;i++){
            int idx = word[i] - 'a';
            if (!p->children[idx]){
                p->children[idx] = new TrieNode();
            }
            p = p->children[idx];
        }
        p->value = ++count;
    }


    bool search2(string &word, int pos, TrieNode* p) {
        if (pos == word.size()){
            return  p->value == 0 ? false: true;
        }else{
            if (word[pos] == '.'){
                for (int j=0;j<26;j++){
                    if (p->children[j]){
                        if (search2(word, pos+1, p->children[j])){
                            return true;
                        }
                    }
                }
                return false;
            }else{
                int idx = word[pos] - 'a';
                if (p->children[idx]){
                    return search2(word, pos+1, p->children[idx]);
                }else{
                    return false;
                }
            }   
        }
    }
        
    // 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 search2(word, 0, trie);
    }
};

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

Code(Python):

class TrieNode:
    def __init__(self):
        self.value = 0
        self.children = [None]*26
    
class WordDictionary:
    
    # initialize your data structure here.
    def __init__(self):
        self.trie = TrieNode()
        self.count = 0

    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        p = self.trie
        for ch in word:
            idx = ord(ch)-ord('a')
            if not p.children[idx]:
                p.children[idx] = TrieNode()
            p = p.children[idx]
        self.count += 1
        p.value = self.count
        

    def search2(self, word, pos, p):
        if pos == len(word):
            if p.value == 0:
                return False
            else:
                return True
        else:
            if word[pos] == '.':
                for pp in p.children:
                    if pp:
                        if self.search2(word, pos+1, pp):
                            return True
                return False
            else:
                idx = ord(word[pos])-ord('a')
                if not p.children[idx]:
                    return False
                else:
                    return self.search2(word, pos+1, p.children[idx])


    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        return self.search2(word, 0, self.trie)
            
        

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