Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:


	WordDictionary()&nbsp;Initializes the object.
	void addWord(word) Adds word to the data structure, it can be matched later.
	bool search(word)&nbsp;Returns true if there is any string in the data structure that matches word&nbsp;or false otherwise. word may contain dots '.' where dots can be matched with any letter.


&nbsp;
Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True


&nbsp;
Constraints:


	1 &lt;= word.length &lt;= 25
	word in addWord consists of lowercase English letters.
	word in search consist of '.' or lowercase English letters.
	There will be at most 3 dots in word for search queries.
	At most 104 calls will be made to addWord and search.


class TrieNode:
    
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.isEnd = False


class WordDictionary:

    def __init__(self):
        self.root = TrieNode("*")
        
    def addWord(self, word: str) -> None:
        
        curr = self.root
        
        for c in word:
            
            if c not in curr.children:
                curr.children[c] = TrieNode(c)
                
            curr = curr.children[c]
        
        curr.isEnd = True
        
    def search(self, word: str) -> bool:
        
        def dfs(root, word):
            curr = root

            for i in range(len(word)):

                if word[i] == ".":
                    for l in curr.children.values():
                        if dfs(l, word[i+1:]) == True:
                            return True
                        
                    return False

                if word[i] not in curr.children:
                    return False

                curr = curr.children[word[i]]

            return curr.isEnd
        
        return dfs(self.root, word)
class WordDictionary {
    private class Node{
        boolean last;
        Node[] sub;
        Node(){
            last = false;
            sub = new Node[26];
        }
    }
    Node root;
    public WordDictionary() {
        root = new Node();
        
    }
    
    public void addWord(String word) {
        Node temp = root;
        for(char c : word.toCharArray()){
            int index = c-'a';
            if(temp.sub[index] == null)
                temp.sub[index] = new Node();
            temp = temp.sub[index];
        }
        temp.last = true;
    }
    
    public boolean search(String word) {
        Node temp = root;
        return dfs(temp, word, 0);
    }
    private boolean dfs(Node node, String word, int i){
        if(i == word.length())
            return node.last;  
        
        int index = word.charAt(i)-'a';
        if(word.charAt(i) == '.'){
            for(int j = 0; j < 26; j++){
                if(node.sub[j] != null)
                    if(dfs(node.sub[j], word, i+1))
                        return true;
            }
            return false;
        }
        else if(node.sub[index] == null)
            return false;
        return dfs(node.sub[index], word, i+1);
    }
}
class WordDictionary {
public:
    struct tr {
        bool isword;
        vector<tr*> next;
        tr() {
            next.resize(26, NULL);
            isword = false;
        }
    };

    tr *root;
    WordDictionary() {
        root = new tr();
    }

    void addWord(string word) {
        tr *cur = root;

        for(auto c: word) {
            if(cur->next[c-'a'] == NULL) {
                cur->next[c-'a'] = new tr();
            }
            cur = cur->next[c-'a'];
        }

        cur->isword = true;
    }

    bool dfs(string& word, int i, tr* cur) {
        if(!cur ){
            return false;
        }

        if(i == word.size()) {
            return cur->isword;
        }

        for (; i < word.size(); i++) {
            char c = word[i];
            if (c == '.') {
                for (auto it: cur->next) {
                    if(dfs(word, i+1, it)) {
                        return true;
                    }
                }
                return false;
            }
            else {
                if(cur->next[c-'a'] == NULL) {
                    return false;
                }
                cur = cur->next[c-'a'];
            }
        }

        return cur->isword;
    }

    bool search(string word) {
        return dfs(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);
 */
var WordDictionary = function() {
    this.aryWordList = [];
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
    this.aryWordList.push(word);
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
    
const isWordsMatch = (first, second) =>
  {
    if (first.length !== second.length) return false;        
      
    if (first.length == 0 && second.length == 0) return true; // Exit case for recursion

    if( first[0] === second[0] || first[0] === "." || second[0] === ".")
        return isWordsMatch(first.substring(1),
                    second.substring(1));

    return false;
}
    
    const isWordFound = () => {
        let isFound = false;
        for(var indexI=0; indexI<this.aryWordList.length; indexI++) {
            
            if(isWordsMatch(this.aryWordList[indexI], word)) { 
                isFound = true;
                break;           
            }
            
        }
        
        return isFound;
    }
    
    return word.indexOf(".") === -1 ? this.aryWordList.includes(word) : isWordFound();
};

/** 
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */
Design Add and Search Words Data Structure