LeetCode Solutions Blog

Design Add and Search Words Data Structure

Number: 211

Difficulty: Medium

Paid? No

Problem Description

Design a data structure that supports adding new words and searching if a string matches any previously added string. The search feature must handle '.' as a wildcard character representing any letter.

Key Insights

Utilize a Trie (prefix tree) to efficiently store words.
Each node in the Trie contains a dictionary for its children and a flag indicating the end of a word.
The search operation is implemented with a depth-first search (DFS) approach.
When the search query contains a dot, explore all possible child nodes.

Space and Time Complexity

Time Complexity:

addWord: O(w), where w is the length of the word.
search: Worst-case O(26^w) for words with multiple wildcards, but practical performance is better given constraints. Space Complexity: O(n * w), where n is the number of words and w is the average word length.

Solution

The WordDictionary is implemented using a Trie. For adding, we insert each character of the word into the Trie. For searching, we use DFS. When encountering a wildcard '.', we recursively search all children nodes. This structure combined with DFS efficiently addresses the wildcard matching and ensures good performance for multiple operations.

Code Solutions

class TrieNode:
    def __init__(self):
        # Dictionary to store child nodes
        self.children = {}
        # Flag to indicate if a word ends here
        self.is_end = False

class WordDictionary:
    def __init__(self):
        # Initialize the Trie with an empty root node
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        # Start at the root of the Trie
        node = self.root
        for char in word:
            # Create a new node if the character is not present
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # Mark the end of the word
        node.is_end = True

    def search(self, word: str) -> bool:
        # DFS helper function
        def dfs(index, node):
            if index == len(word):
                return node.is_end
            char = word[index]
            if char == '.':
                # If wildcard, search all children nodes
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True
                return False
            else:
                # If character not found, word does not exist
                if char not in node.children:
                    return False
                return dfs(index + 1, node.children[char])
        return dfs(0, self.root)

# Example usage:
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # Output: False
print(wd.search("bad"))  # Output: True
print(wd.search(".ad"))  # Output: True
print(wd.search("b.."))  # Output: True