211. Design Add and Search Words Data Structure

211. Design Add and Search Words Data Structure#

Difficulty: Medium

Link to Problem: To see the Design Add and Search Words Data Structure problem on LeetCode, click here!

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Constraints:

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most \(10^4\) calls will be made to addWord and search.

Probelm Explanation:#

The problem is to design a data structure called WordDictionary that allows you to add words and search for words efficiently. The key feature of this data structure is that it should support wildcard search, where a dot (‘.’) can match any letter.

Here are the specific requirements and explanations for the problem:

Initialize the WordDictionary object using the constructor WordDictionary().
The addWord(word) method allows you to add a word to the data structure. Once added, you should be able to search for this word later. The words consist of lowercase English letters, and each word has a length between 1 and 25 characters.
The search(word) method allows you to search for a word in the data structure. This method returns True if there is any string in the data structure that matches the given word or False otherwise. The word you are searching for may contain dots (‘.’), where each dot can match any letter.
The wildcard character (‘.’) in the search method allows for partial or fuzzy searching. For example, if the word dictionary contains the words “bad,” “dad,” and “mad,” then:
- Searching for “pad” should return False because there is no exact match.
- Searching for “bad” should return True because “bad” is in the dictionary.
- Searching for “.ad” should return True because it can match “bad,” “dad,” or “mad.”
- Searching for “b..” should return True because it can match “bad,” “bed,” “bet,” etc.
The problem specifies that there will be at most two dots (‘.’) in search queries, and there will be at most 10^4 calls to both addWord and search.

In summary, you need to implement the WordDictionary class that efficiently supports adding words and searching for words, where the search can include wildcard characters (‘.’) that match any letter.

Solution:#

Here’s a Python function to implement this algorithm:

class TrieNode:
    def __init__(self):
        # Initialize a TrieNode with children and a flag to indicate the end of a word.
        self.children = {}
        self.is_end_of_word = False

class WordDictionary:

    def __init__(self):
        # Initialize the WordDictionary with a root node.
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        # Iterate through the characters in the word.
        for char in word:
            if char not in node.children:
                # Create a new node for the character if it doesn't exist.
                node.children[char] = TrieNode()
            # Move to the next node.
            node = node.children[char]
        # Mark the end of the word by setting the flag to True.
        node.is_end_of_word = True

    def search_helper(self, node: TrieNode, word: str) -> bool:
        if not word:
            # If there are no characters left in the word, check if we reached the end of a word in the trie.
            return node.is_end_of_word
        
        char = word[0]
        if char == '.':
            # If the character is a dot, explore all possible child nodes.
            for child in node.children.values():
                if self.search_helper(child, word[1:]):
                    return True
        elif char in node.children:
            # If the character is in the children of the current node, move to the next node.
            return self.search_helper(node.children[char], word[1:])
        
        # If the character is not found and is not a dot, the word is not in the trie.
        return False

    def search(self, word: str) -> bool:
        # Start the search from the root of the trie.
        return self.search_helper(self.root, word)

Explanation:#

This code defines a WordDictionary class that uses a Trie data structure to efficiently store and search for words. Here’s a step-by-step explanation:

TrieNode class: This class represents nodes in the Trie data structure. Each node has two attributes: children (a dictionary to store child nodes) and is_end_of_word (a flag to indicate whether the node marks the end of a word).
WordDictionary class: This class initializes with an empty Trie by creating a root node.
addWord method: This method adds a word to the Trie. It iterates through each character in the word and creates Trie nodes as necessary. It sets the is_end_of_word flag to True for the final character of the word to mark the end of the word.
search_helper method: This is a recursive helper function for searching words in the Trie. It takes a Trie node (node) and a word to search (word) as input. If there are no characters left in the word (not word), it checks if the current node marks the end of a word. If it does, it returns True.
If the first character of the word is a dot (‘.’), the function explores all possible child nodes by iterating through node.children.values() and recursively calls search_helper for each child with the remaining part of the word (word[1:]).
If the first character of the word is not a dot and is found in the children of the current node, the function recursively moves to the next node by calling search_helper on the child node and the remaining part of the word.
If the character is not found in the children and is not a dot, the word is not in the Trie, so the function returns False.
search method: This is the public method for searching words. It initiates the search process by calling search_helper starting from the root node of the Trie.

Overall, this code efficiently implements a Trie-based data structure that allows adding and searching for words, including support for wildcard characters represented by dots (‘.’).

Test cases:#

Here’s how you can use this solution:

# Example 1: 

# Example usage:

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

False
True
True
True

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the WordDictionary class methods:

addWord Method:
- Time Complexity: O(L)
  - L is the length of the word being added.
  - In the worst case, we need to iterate through each character in the word and create nodes in the Trie. This takes O(L) time.
- Space Complexity: O(L)
  - The space complexity for storing the word in the Trie is also O(L) because we create nodes for each character in the word.
search_helper Method (called by search):
- Time Complexity: O(2^M * L)
  - M is the maximum number of dots (‘.’) in the search word.
  - In the worst case, when there are M dots in the search word, we may explore all possible child nodes at each dot. This results in a branching factor of 26 (for lowercase letters) at each dot.
  - So, the time complexity is exponential in the number of dots and linear in the length of the word being searched (L).
- Space Complexity: O(L)
  - The space complexity for the recursive call stack is O(L) in the worst case because we may have to recurse to a depth equal to the length of the search word.
search Method:
- Time Complexity: O(2^M * L)
  - The search method calls the search_helper method, which has the same time complexity explained above.
- Space Complexity: O(L)
  - The space complexity for the recursive call stack is O(L) in the worst case, as explained earlier.

Overall, the time complexity of the search method is mainly affected by the number of dots (‘.’) in the search word. In the worst case, when there are multiple dots and many possibilities to explore at each dot, the time complexity can be exponential. However, for most practical cases, it performs reasonably well.

The space complexity primarily depends on the space required to store the words in the Trie. It is proportional to the total number of characters in all added words and is linear with respect to the length of the words added.

In summary:

Time Complexity for addWord: O(L)
Time Complexity for search: O(2^M * L)
Space Complexity: O(L) for storing words in the Trie, O(L) for the recursive call stack during search.

Note: The space complexity analysis assumes that the dictionary contains a reasonable number of words and does not account for the overhead of Python objects or system-level memory allocation.

Challenging Exercises:#

Dictionary Auto-Completion: Extend the WordDictionary class to provide auto-completion suggestions based on the prefix of a word. Implement a method that returns a list of words that match the given prefix.
Support Word Deletion: Extend the WordDictionary class to support word deletion. Add a method deleteWord(word) that removes a word from the data structure. Ensure that the search operation still works correctly after deletion.