211. Design Add and Search Words Data Structure

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


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        def search_in_node(node, word):
            for i, char in enumerate(word):
                if char not in node.children:
                    if char == ".":
                        for child in node.children:
                            if search_in_node(node.children[child], word[i + 1 :]):
                                return True
                    return False
                else:
                    node = node.children[char]
            return node.is_end

        return search_in_node(self.root, word)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

# class WordDictionary:

#     def __init__(self):
#         self.word_set = set()

#     def addWord(self, word: str) -> None:
#         self.word_set.add(word)
#         for i in range(len(word)):
#             # Add all possible variations with a '.' in each position
#             self.word_set.add(word[:i] + '.' + word[i + 1:])

#     def search(self, word: str) -> bool:
#         if word in self.word_set:
#             return True

#         # Check if the word contains a '.'
#         if '.' not in word:
#             return False

#         # Split the word into two parts at the first occurrence of '.'
#         first_part, rest_part = word.split('.', 1)

#         # Iterate over lowercase letters and create variations to search
#         for char in 'abcdefghijklmnopqrstuvwxyz':
#             new_word = first_part + char + rest_part
#             if new_word in self.word_set:
#                 return True

#         return False

Solution from kamyu104/LeetCode-Solutions · MIT