211. Add and Search Word Data structure design - cocoder39/coco39_LC GitHub Wiki

class Trie:
    def __init__(self):
        self.isWord = False
        self.children = collections.defaultdict(Trie)

class WordDictionary:

    def __init__(self):
        self.root = Trie()
        
    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children[ch]
        node.isWord = True

    def search(self, word: str) -> bool:
        return self.helper(self.root, word)

    def helper(self, node, word):
        for i, ch in enumerate(word):
            if ch != '.':
                node = node.children.get(ch)
                if node is None:
                    return False
            else:
                for _, child in node.children.items():
                    if self.helper(child, word[i+1:]):
                        return True
                return False
        return node.isWord

class WordDictionary {
public:
    class TriNode {
    public:
        bool isKey;
        vector<TriNode*> children;
        TriNode() : isKey(false), children(vector<TriNode*>(26, nullptr)) {};
    };

    WordDictionary() {
        root = new TriNode();
    }

    // Adds a word into the data structure.
    void addWord(string word) { //O(len)
        TriNode* p = root;
        for (auto c : word) {
            if ((p->children)[c - 'a'] == nullptr)
                (p->children)[c - 'a'] = new TriNode();
            p = (p->children)[c - 'a'];
        }
        p->isKey = 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 search_helper(word, 0, root);
    }
private:
    TriNode* root;
    
    bool search_helper(string& word, int start, TriNode* p) { //worse case O(26^len), eg. '....' matches 'zz..'
        if (start == word.length()) 
            return p->isKey;
        
        if (word[start] != '.') {
            p = (p->children)[word[start] - 'a'];
            return (p && search_helper(word, start + 1, p));
        }
        else {
            for (int i = 0; i < 26; i++) {
                TriNode* node = (p->children)[i];
                if (node && search_helper(word, start + 1, node))
                    return true;
            }
            return false;
        }
    }
};

class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* p = root;
        for (auto c : word) {
            int idx = c - 'a';
            if (! (p->child)[idx])    (p->child)[idx] = new TrieNode();
            p = p->child[idx];
        }
        p->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 searchHelper(word, 0, root);
    }
    
    class TrieNode {
    public:
        bool isWord;
        vector<TrieNode*> child;
        TrieNode() {
            isWord = false;
            child = vector<TrieNode*>(26, nullptr);
        }
    };
private:
    TrieNode* root;   
    
    bool searchHelper(string& word, int start, TrieNode* cur) { //cur points to root/word[start-1]
        if (start == word.length()) { //cur points to last char
            return cur->isWord;
        }
        
        for (int i = start; i < word.length(); i++) {
            if (word[i] == '.') {
                for (int j = 0; j < 26; j++) {
                    if (cur->child[j] && searchHelper(word, i + 1, cur->child[j])) {
                        return true;
                    }
                }
                return false;
            } else {
                int idx = word[i] - 'a';
                if (! cur->child[idx])  return false;
                cur = cur->child[idx];
            }
        }
        return cur->isWord;
    }
};

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        cur = self.root
        for ch in word:
            cur = cur.children[ch]
        cur.is_word = True

    def search2(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        return self.search_trie(word, self.root)
    
    def search_trie(self, word: str, node: TrieNode):
        for i, ch in enumerate(word):
            if ch is not '.':
                node = node.children.get(ch)
                if node is None:
                    return False
            else:
                for key, val in node.children.items():
                    if self.search_trie(word[i+1:], val):
                        return True
                return False
        return node.is_word
   
    def search1(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        queue = collections.deque()
        queue.append(self.root)
        for ch in word:
            if not queue:
                return False
            sz = len(queue)
            for i in range(sz):
                cur = queue.popleft()
                if ch != '.':
                    next_node = cur.children.get(ch)
                    if next_node is not None:
                        queue.append(next_node)
                else:
                    for key, val in cur.children.items():
                        queue.append(val)
        
        while queue:
            cur = queue.pop()
            if cur.is_word:
                return True
        return False