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.

Examples

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

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 10^4 calls to addWord and search.

Thinking Process

  1. Trie Foundation: Builds on standard Trie structure
  • DFS explores one branch fully before backtracking.
  • Mark visited nodes to avoid cycles on graphs.
  • Return aggregated results from children to the parent.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

struct TrieNode :
dict[char, TrieNode> children
bool isWord = False
class WordDictionary:
WordDictionary() :
root = new TrieNode()
~WordDictionary() :
deleteTrie(root)
def addWord(self, word):
    TrieNode node = root
    for ch in word:
        if not node.ch in children:
            node.children[ch] = new TrieNode()
        node = node.children[ch]
    node.isWord = True
def search(self, word):
    return searchInNode(word, 0, root)
TrieNode root
def searchInNode(self, word, idx, node):
    if(not node) return False
    if(idx == len(word)) return node.isWord
    char curr = word[idx]
    if curr == '.':
        for([_, child]: node.children) :
        if searchInNode(word, idx + 1, child):
            return True
    return False
if(not node.curr in children) return False
return searchInNode(word, idx + 1, node.children[curr])
def deleteTrie(self, node):
    if(not node) return
    for([_, child]: node.children) :
    deleteTrie(child)
delete node
/
 Your WordDictionary object will be instantiated and called as such:
 WordDictionary obj = new WordDictionary()
 obj.addWord(word)
 bool param_2 = obj.search(word)
/

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Trie Foundation: Builds on standard Trie structure

How the code works:

  1. Trie Foundation: Builds on standard Trie structure
    • DFS explores one branch fully before backtracking.
    • Mark visited nodes to avoid cycles on graphs.
    • Return aggregated results from children to the parent.

      Common Mistakes

  2. Single wildcard: search(".") when no single-letter words exist
  3. All wildcards: search("...") explores all 3-letter words
  4. Wildcard at start: search(".ad") matches “bad”, “dad”, “mad”
  5. Wildcard at end: search("ba.") matches “bad”, “bat”, etc.
  6. No match: search("xyz") returns false correctly
  7. Empty word: Not applicable (constraints guarantee length ≥ 1)

  8. Multiple wildcards: search("b..") handles multiple wildcards

  9. Not handling null nodes: Forgetting to check if node exists before accessing
  10. Incorrect base case: Not checking idx == word.size() before checking isWord
  11. Wildcard logic: Not trying all children when encountering '.'
  12. Memory leaks: Forgetting to implement destructor
  13. Early exit: Not returning immediately when match found in wildcard search
  14. Index management: Off-by-one errors in recursive calls

When to Use This Structure

  1. Word Search with Wildcards: Pattern matching in dictionaries
  2. Autocomplete with Partial Input: When users type incomplete words
  3. Spell Checker: Finding similar words with wildcards
  4. Text Search: Searching documents with pattern matching
  5. Game Development: Word games like Scrabble, Boggle
  6. Search Engines: Prefix-based search with pattern support

This problem extends the Trie data structure with wildcard search capabilities. The key is using DFS to explore all possible paths when encountering wildcard characters, making it useful for pattern matching and flexible word search applications.

Key Takeaways

  1. Trie Foundation: Builds on standard Trie structure
  2. Wildcard Handling: DFS explores all paths when encountering '.'
  3. Early Termination: Returns true immediately when match found
  4. Memory Safety: Destructor prevents memory leaks
  5. Map vs Array: Using unordered_map is more flexible but slightly slower than array
  6. Recursive Search: Clean recursive approach for wildcard matching

References

Template Reference