211: Beats 99.15% and Beats 97.15%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe WordDictionary class is a data structure that supports adding new wor
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe WordDictionary class is a data structure that supports adding new words and searching if a string matches any previously added string.\n\nThe class has three methods:\n\n- __init__(self): Initializes the object and creates a defaultdict of sets to store the words. The keys of the dictionary are the length of the words, and the values are sets of words of that length.\n- addWord(self, word: str) -> None: Adds a word to the data structure by inserting it into the set of words with the same length in the dictionary.\n- search(self, word: str) -> bool: Searches for a word in the data structure. If the word doesn\'t contain a dot character \'.\', it checks if the word exists in the set of words with the same length. If the word contains dots, it iterates over all words of the same length and checks if each character in the word matches the corresponding character in the word being searched, except for the dots.\n\n# Complexity\n- Time complexity:\nBeats\n99.15%\n\n- Space complexity:\nBeats\n97.15%\n\n# Code\n```\nfrom collections import defaultdict\n\nclass WordDictionary:\n\n    def __init__(self):\n        """ Initialize your data structure here. """\n        # create a defaultdict of sets to store the words\n        # keys are word lengths, values are sets of words of that length\n        self.dic = defaultdict(set)\n\n    def addWord(self, word: str) -> None:\n        """ Adds a word into the data structure. """\n        # add the word to the set of words with the same length\n        self.dic[len(word)].add(word)\n\n    def search(self, word: str) -> bool:\n        """ Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. """\n        # if the word doesn\'t contain dots, check if it exists in the set of words with the same length\n        if \'.\' not in word:\n            return word in self.dic[len(word)]\n        # if the word contains dots, iterate over all words of the same length\n        for v in self.dic[len(word)]:\n            # check if each character in the word matches the corresponding character in the word being searched, except for the dots\n            for i, ch in enumerate(word):\n                if ch != v[i] and ch != \'.\':\n                    break\n            else:\n                return True\n        # if no matching word is found, return False\n        return False\n\n```
['String', 'Depth-First Search', 'Design', 'Python', 'Python3']