LeetCode 211: Design Add And Search Words Data Structure — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Trie | Design | String | Backtracking

The Problem

Design a data structure that supports adding words and searching for words with wildcard '.' characters that can match any single letter.

Approach

Uses a Trie (prefix tree) data structure to store words efficiently. For searching, implements recursive backtracking when encountering '.' wildcards to explore all possible character branches in the trie.

Time: O(n) for addWord, O(n × 26^m) for search where n is word length and m is number of dots · Space: O(ALPHABET_SIZE × N × M) where N is number of words and M is average word length

Code

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