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.
• 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.

Additional information

• 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.

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

Brute Force (Length-Indexed Hash Map)

Intuition

The simplest way to store words is in a list. However, scanning every single word whenever a search is called is incredibly slow. We can optimize this naive approach by using a Hash Map where the key is the length of the word, and the value is a list of all words of that length.

When search is called, we immediately filter out all words that aren't the exact same length as our target. We then loop through the remaining words and compare them character by character, treating . as an automatic match.

Algorithm

1. Initialize: Create an empty words dictionary.
2. addWord: Find the length n of the word. If n is not in the dictionary, add an empty list. Append word to self.words[n].
3. search: * Find the length n of the target word. If n is not a key in the dictionary, return False.
   • Loop through every string w in self.words[n].
   • Compare w and word character by character.
   • If the characters don't match AND the character in word is not a ., mark as a mismatch and break.
   • If you make it through the whole string without a mismatch, return True.
4. If the loop finishes checking all words of length n without finding a match, return False.

class WordDictionary:
    def __init__(self):
        # Maps length of word -> list of words
        self.words = {}

    def addWord(self, word: str) -> None:
        n = len(word)
        if n not in self.words:
            self.words[n] = []
        self.words[n].append(word)

    def search(self, word: str) -> bool:
        n = len(word)
        if n not in self.words:
            return False
            
        for w in self.words[n]:
            match = True
            for i in range(n):
                # If characters differ and it's not a wildcard
                if word[i] != '.' and word[i] != w[i]:
                    match = False
                    break
            if match:
                return True
                
        return False

Time & Space Complexity

• Time complexity: * addWord: O(1).
  • search: O(N * M), where N is the number of words of the exact same length, and M is the length of the word.
• Space complexity: O(W) where W is the total number of characters across all words stored in the dictionary.

Trie with DFS Backtracking - Optimal

Intuition

While the Hash Map approach is decent, it still forces us to scan entire words repeatedly. We can achieve massive performance gains by using a Trie (Prefix Tree). Words that share prefixes will share the exact same nodes in memory.

The only tricky part is the . wildcard. In a standard Trie search, we just look up the character in the node's children. If the character is a ., we don't know which path to take! Therefore, we must take all available paths. We can use a recursive Depth-First Search (DFS). When we hit a ., we recursively call our search function on every single child node. If any of those paths successfully reach the end of the word, we return True.

Algorithm

1. Define Node: Create a TrieNode class with a children dictionary and an is_end boolean.
2. Initialize: Create a self.root TrieNode.
3. addWord: Standard Trie insertion. Traverse down the tree, creating nodes for missing characters, and mark the final node with is_end = True.
4. search: Define a recursive helper function dfs(index, root):
   • Start a pointer curr = root.
   • Loop i from index to the end of the word.
   • If the character char is a .:
     • Loop through every child node inside curr.children.values().
     • Recursively call dfs(i + 1, child). If any return True, instantly return True.
     • If all child paths fail, return False.
   • If the character is a normal letter:
     • If it's not in curr.children, return False.
     • Move the pointer down: curr = curr.children[char].
   • After the loop finishes, return curr.is_end.
5. Call dfs(0, self.root) to trigger the search.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end = True

    def search(self, word: str) -> bool:
        
        def dfs(j, root):
            curr = root
            for i in range(j, len(word)):
                char = word[i]
                
                # If wildcard, explore ALL possible child paths
                if char == '.':
                    for child in curr.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                
                # If normal character, follow the standard path
                else:
                    if char not in curr.children:
                        return False
                    curr = curr.children[char]
                    
            return curr.is_end
            
        return dfs(0, self.root)

Time & Space Complexity

• Time complexity: * addWord: O(M) where M is the length of the word.
  • search: O(M) for a word without dots. In the absolute worst case (a word consisting entirely of .......), it is O(26^M) as it explores every node in the tree. However, with the constraints (at most 2 dots), the branching is heavily pruned.
• Space complexity: O(W) where W is the total number of characters across all words, perfectly optimized by shared prefixes.