We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Add and Search Words Data Structure

Difficulty: Medium

Problem Description

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class with methods to add words and search for them, where the search may include wildcards represented by dots.

Key Insights

  • The data structure needs to efficiently handle insertions and searches.
  • A Trie (prefix tree) is well-suited for this problem as it allows for efficient storage and retrieval of strings.
  • Dots in the search can represent any character, requiring a depth-first search approach to explore possible matches.

Space and Time Complexity

Time Complexity:

  • addWord: O(m), where m is the length of the word being added.
  • search: O(m), where m is the length of the word being searched. In the worst case, it may require checking multiple branches in the Trie for dots.

Space Complexity: O(n * m), where n is the number of words added and m is the maximum length of a word.

Solution

The solution involves using a Trie data structure to store each word added to the WordDictionary. Each node in the Trie represents a character, and the path from the root to a node represents a prefix of the words in the dictionary. When searching for a word, we can traverse the Trie, and when a dot is encountered, we explore all possible children nodes at that position, allowing for a flexible search mechanism.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = 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_of_word = True

    def search(self, word: str) -> bool:
        return self._search_in_node(word, self.root)

    def _search_in_node(self, word: str, node: TrieNode) -> bool:
        for i, char in enumerate(word):
            if char == '.':
                for child in node.children.values():
                    if self._search_in_node(word[i + 1:], child):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                node = node.children[char]
        return node.is_end_of_word
← Back to All Questions