<jupyter_start><jupyter_text>Design Add and Search Words Data StructureDesign a data structure that supports adding new words and finding if a string matches any previously added string.Implement the WordDictionary class:- WordDictionary() Initializes the object.- void addWord(word) Adds word to the data structure, it can be matched later.- bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. - word may contain dots '.' where dots can be matched with any letter.<jupyter_code>class WordDictionary:
    def __init__(self):
        self.trie = {}
        
    def addWord(self, word: str) -> None:
        curr = self.trie
        
        for c in word:
            res = curr.get(c, {})
            curr[c] = res
            curr = res
        curr['$'] = {}

        
    def search(self, word: str) -> bool:
        def _search(node, word):
            if not word:
                return True if '$' in node else False
            elif word[0] in node:
                return _search(node[word[0]], word[1:])
            elif word[0] == '.':
                res = []
                for k in node.keys():
                    res.append(_search(node[k], word[1:]))
                return any(res)
            else:
                return False
            
        return _search(self.trie, word)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09188801148600144, 'fraction_numerical': 0.003589375448671931, 'mean_word_length': 1.9163179916317992, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '43618', 'license': 'MIT', 'n_tokens_mistral': 375, 'n_tokens_neox': 364, 'n_words': 140, 'path': 'python-data-structures/interview-fb/design-add-search-words.ipynb', 'repo_name': 'dimastatz/ml-workshop', 'size': '1393'}