Design Add And Search Words Data Structure - Leetcode Solution

Design Add And Search Words Data Structure problem on LeetCode can be solved using Trie data structure. The problem statement requires us to design a data structure that supports adding and searching for words. The search operation can also have wildcard characters represented by a ‘.’, which can match any character.

Let's start by understanding Trie data structure. Trie or prefix tree is a tree-based data structure used to store a collection of strings efficiently. Each node in the Trie represents a prefix of a word. The root represents an empty string, and each edge is labeled with a character. The child nodes represent prefixes formed by appending characters to the prefix of the parent node.

The solution involves building a Trie tree of words. Since we need to support wildcard search, we add an extra condition to the Trie node, which checks if the node has a wildcard character (‘.’) as a child.

The data structure will have two main operations:

1. addWord(word): This operation will add a new word to the Trie tree. We iterate over each character of the word and add each character as a new node in the Trie. We mark the last node of the word as an end of word node.

2. search(word): This operation will search for the given word in the Trie tree. We iterate over each character of the word and check if the character exists in the current node’s children. If the character exists, we move to that node and continue the search. If the character is ‘.’, we search all the children of the current node and move to the next character.

The search operation also needs to check for wildcard characters. To support this, we explore all the children of the current node for wildcard characters recursively until we find a match or reach the end of the Trie.

Here is the Python implementation of the data structure:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False
        self.isWildcard = False
        
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEndOfWord = True
        
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        return self.searchRecursive(word, self.root)
    
    def searchRecursive(self, word: str, node: TrieNode) -> bool:
        if not word:
            return node.isEndOfWord
        char = word[0]
        if char != ".":
            if char not in node.children:
                return False
            return self.searchRecursive(word[1:], node.children[char])
        else:
            for child in node.children.values():
                if self.searchRecursive(word[1:], child):
                    return True
            return False

Time Complexity:

Add O(m), where m is the length of the word being added.

Search O(n26^m), where n is the number of words in the Trie and m is the length of the searched word. The complexity is at most n26^m, since for each of the n words in the Trie, we can potentially recurse down all the children nodes (26 branching factors at each node), representing all possible combinations of the search word with wildcard characters.

Space Complexity:

O(nm26), where n is the number of words, m is the average length of the word, and 26 is the size of the English alphabet. The space complexity comes from storing the Trie nodes. Note that this can be optimized by compressing the Trie using techniques like suffix tree.

1