Design Add and Search Words Data Structure medium

Problem Statement

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.
• addWord(word) Adds word to the data structure.
• 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.

Example 1:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Example 2:

Input
["WordDictionary","addWord","search"]
[[],["a"],["."]]
Output
[null,null,false]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("a");
wordDictionary.search("."); // return False

Steps:

1. Data Structure: We'll use a Trie (prefix tree) to efficiently store and search words. A Trie is particularly well-suited for this problem because it allows for prefix-based searches.

2. addWord(word): Traverse the Trie, adding nodes for each character in the word. Mark the end of a word with a special flag (e.g., is_word = True).

3. search(word): This is the more complex part. We'll recursively traverse the Trie.

   • If a character is a letter, we simply move to the corresponding child node.
   • If a character is a '.', we recursively explore all child nodes.
   • We reach the end of the word if we've processed all characters. If the current node has is_word = True, we've found a match.

Explanation:

The Trie efficiently handles both adding words and searching for words with wildcard characters ('.'). Adding a word is O(word length) because we traverse the tree once. Searching is also relatively efficient, though its worst-case time complexity depends on the number of wildcard characters and the branching factor of the Trie.

Code:

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

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

    def _search(self, word, node):
        if not word:
            return node.is_word
        
        char = word[0]
        if char == '.':
            for child in node.children.values():
                if self._search(word[1:], child):
                    return True
            return False
        else:
            if char in node.children:
                return self._search(word[1:], node.children[char])
            else:
                return False

Complexity:

• Time complexity:

  • addWord(word): O(L), where L is the length of the word.
  • search(word): In the worst case (many dots and many words in the Trie), it could be O(B^L), where B is the branching factor of the Trie (number of possible characters) and L is the length of the word. However, in practice, it's often much faster.

• Space complexity: O(N * L), where N is the number of words added and L is the average length of the words. This is due to the space used by the Trie.