# 211. 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.

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

Approach 1: use a trie.

# Code (Python)

Approach 1:

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = {}

class WordDictionary:

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

    def addWord(self, word: 'str') -> 'None':
        """
        Adds a word into the data structure.
        """
        node = self._trie
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True

    def search(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(0, word, self._trie)
    
    def _search(self, index, word, node):
        if index == len(word):
            return node.is_word
        char = word[index]
        if char != '.':
            if char not in node.children:
                return False
            return self._search(index + 1, word, node.children[char])
        else:
            for child_node in node.children.values():
                if self._search(index + 1, word, child_node) == True:
                    return True
            return False

# Code (C++)

Approach 1:

class WordDictionary {
private:
    struct TrieNode {
        TrieNode *children[26];
        bool isEnd;
        TrieNode() {
            for (int i = 0; i < 26; ++i)
            {
                children[i] = NULL;
            }
            isEnd = false;
        }
    };
    
    TrieNode *root;
    
    bool doSearch(string word, int index, TrieNode *start) {
        if (start == NULL)
            return false;
        if (index == word.size())
            return start->isEnd;
        TrieNode *curr = start;    
        int head = 0;
        int tail = 25;
        if (word[index] != '.')
        {
            head = word[index] - 'a';
            tail = head;
        }
        for (int j = head; j <= tail; ++j)
        {
            if (doSearch(word, index+1, curr->children[j]))
                return true;
        }
        return false;
    }

public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode *curr = root;
        for (int i = 0; i < word.size(); ++i)
        {
            int j = word[i] - 'a';
            if (curr->children[j] == NULL)
                curr->children[j] = new TrieNode();
            curr = curr->children[j];
        }
        curr->isEnd = 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 doSearch(word, 0, root);
    }
};

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