10.6 Design Add and Search Words Data Structure

10.6.1 Problem Metadata

10.6.2 Description

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.

10.6.3 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

10.6.4 Constraints

  • \(1 \le\) word.length \(\le\) 25
  • word in addWord consists of lowercase English letters
  • word in search consists 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

10.6.5 Solution - Trie with DFS

10.6.5.1 Walkthrough

This problem requires a data structure that efficiently stores words and supports pattern matching with wildcard characters. A Trie (prefix tree) combined with DFS/backtracking provides the optimal solution.

Core Data Structure - Trie: - Each TrieNode contains a map of children (character → TrieNode) and a boolean flag marking word endings - Words share common prefixes, making storage and lookup efficient - The trie structure naturally supports prefix-based operations

Key Challenge - Wildcard Matching: The wildcard character '.' can match any single letter, requiring us to explore multiple branches simultaneously. When we encounter a '.': - We cannot follow a single deterministic path - We must try all possible children at that position using DFS - If any branch leads to a valid word, return true

Algorithm Approach:

  1. addWord(word): Standard trie insertion
    • Start at root, traverse/create nodes for each character
    • Mark the final node as end of word
  2. search(word): Two cases at each position
    • Regular character: Follow the single matching child (or fail if none exists)
    • Wildcard ‘.’: Recursively try all children with the remaining substring

Visual Example with words = [“bad”, “dad”, “mad”]:

Trie structure after adding all words:
        root
       /  |  \
      b   d   m
      |   |   |
      a   a   a
      |   |   |
      d*  d*  d*

(* marks end of word)

Search "pad":
  root → 'p' not found → return false

Search "bad":
  root → 'b' → 'a' → 'd'* → true

Search ".ad":
  root → '.' → try all children (b, d, m)
    ├─ 'b' → search "ad" from node 'b'
    │   └─ 'a' → 'd'* → true ✓ (found!)
    └─ (no need to continue, already found match)

Search "b..":
  root → 'b' → '.' → try all children (only 'a')
    └─ 'a' → search "." from node 'a'
        └─ '.' → try all children (only 'd')
            └─ 'd'* → true ✓

Implementation Details:

The solution uses a helper method searchWildCard() to handle wildcard exploration: - When encountering '.', extract the remaining substring - Try searching the remaining substring from each child of the current node - Return true if any recursive call succeeds (DFS short-circuit)

Example trace for search(“.ad”) with words [“bad”, “dad”, “mad”]:

search(".ad", root):
  i=0, ch='.'
  → searchWildCard(".ad", 0, root)
      subword = "ad"
      children = {b, d, m}

      Try child 'b':
        search("ad", node_b)
          i=0, ch='a' → node_b.children.get('a') = node_a
          i=1, ch='d' → node_a.children.get('d') = node_d
          node_d.isEndOfWord = true
          → return true ✓

      (short-circuit, no need to try 'd' and 'm')

  Result: true

10.6.5.2 Analysis

  • Time Complexity:
    • addWord(word): O(m) where m is the length of the word
      • Iterate through each character exactly once
      • HashMap putIfAbsent and get operations are O(1) average case
    • search(word): Depends on number of wildcards
      • Best case (no wildcards): O(m) - deterministic path through trie
      • Worst case (all wildcards): O(26^m) - must explore all branches at each position
      • Average case: O(26^k × m) where k is the number of wildcards (problem states at most 2)
      • With constraint of at most 2 wildcards: O(26^2 × m) = O(676m), effectively O(m)
  • Space Complexity: O(N × M) where N is total number of words and M is average word length
    • Trie storage: Each word adds at most M new nodes (shared prefixes reduce this)
    • HashMap overhead: Each TrieNode uses a HashMap (more memory than array but sparse)
    • Recursion stack for search: O(m) depth for DFS calls

Design Trade-offs:

Aspect HashMap Children Array[26] Children
Memory per node Higher (HashMap overhead) Lower (fixed 26 slots)
Memory efficiency Better for sparse tries Better for dense tries
Access time O(1) average, slightly slower O(1) constant
Code clarity More intuitive More performant

The HashMap approach is valid and provides good sparse memory usage when the trie has few branches per node.

10.6.5.3 Implementation Steps

  1. Define TrieNode inner class:
    • Map<Character, TrieNode> children to store child nodes
    • boolean isEndOfWord flag to mark complete words
    • Constructor initializes empty HashMap and sets flag to false
  2. Initialize WordDictionary:
    • Create a root TrieNode in the constructor
  3. Implement addWord(word):
    • Start at root node
    • For each character in word:
      • Use putIfAbsent(ch, new TrieNode()) to create child if doesn’t exist
      • Move current pointer to child node
    • Mark final node as isEndOfWord = true
  4. Implement search(word):
    • Create public method that delegates to helper: search(word, root)
    • Helper method iterates through word characters:
      • If character is '.': call searchWildCard() to explore all branches
      • If regular character: follow single child path or return false if not found
    • After processing all characters, return current.isEndOfWord
  5. Implement searchWildCard(word, index, root):
    • Extract remaining substring: subword = word.substring(index + 1)
    • Iterate through all children of current node
    • For each child, recursively call search(subword, child)
    • Return true if any recursive call succeeds (DFS short-circuit)
    • Return false if all children fail

10.6.5.4 Code - Java

class WordDictionary {

    private class TrieNode {
        Map<Character, TrieNode> children;
        boolean isEndOfWord;

        TrieNode() {
            children = new HashMap<>();
            isEndOfWord = false;
        }
    }

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        return search(word, root);
    }

    private boolean search(String word, TrieNode start) {
        TrieNode current = start;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (ch == '.') {
                // Wildcard: explore all possible branches
                return searchWildCard(word, i, current);
            } else {
                current = current.children.get(ch);
                if (current == null) {
                    return false;
                }
            }
        }
        return current.isEndOfWord;
    }

    private boolean searchWildCard(String word, int index, TrieNode root) {
        TrieNode current = root;
        String subword = word.substring(index + 1);

        // Try all possible children for the wildcard position
        for (TrieNode child : current.children.values()) {
            if (search(subword, child)) {
                return true;  // Short-circuit on first match
            }
        }

        return false;
    }
}