Design Add and Search Words Data Structure

Problem Statement

Design a data structure that supports adding words and searching for words with support for the ’.’ wildcard character.

Implement the WordDictionary class:

• addWord(word) — Adds word to the data structure without duplicates.
• search(word) — Returns true if there is any word in the data structure that matches word. word may contain dots ’.’ where each dot can represent any single letter.

What to notice first

• The ’.’ wildcard can match any single character — you must explore all branches.
• This is a Trie with backtracking for wildcard resolution.
• When you encounter a ’.’, recursively search all child branches.
• Exact character matches follow a direct path.

Examples

Operation	Input	Output	State
AddWord	”bad”	—	Trie has: b→a→d
AddWord	”dad”	—	Trie has: d→a→d, b→a→d
AddWord	”mad”	—	Trie has: m→a→d, d→a→d, b→a→d
Search	”pad”	false	No word starting with p
Search	”bad”	true	Exact match found
Search	”.ad”	true	’.’ matches ‘b’, ‘d’, or m
Search	”b..“	true	’.’ matches ‘a’, then d

Constraints

• 1 <= word.length <= 500
• word in addWord consists of lowercase English letters.
• word in search consists of lowercase English letters and dots ’.’.
• At most 5000 calls will be made to addWord and search.

Real-World Applications

Where this pattern appears

• Fuzzy search / autocomplete — match words with missing characters.
• Regex engines — implement simple wildcard matching.
• DNS name resolution — match domain patterns.
• Security filters — detect malware using pattern-based signatures.
• Database queries — wildcard-based string matching in SQL-like engines.

Complexity Comparison

Approach	AddWord	Search	Space
Recursive DFS	O(m)	O(n × 26^m)	O(m × 26)
Iterative BFS	O(m)	O(n × 26^m)	O(m × 26)

m = word length, n = number of words, search worst-case with many wildcards

Which approach should you learn first?

• Pick Recursive DFS for interview clarity — easier to explain the backtracking logic.
• Pick Iterative BFS if you prefer avoiding recursion or have deep trees.

Clearer Logic

Recursive DFS

O(m) insert · O(n×26^m) search

Avoids Recursion

Iterative BFS

O(m) insert · O(n×26^m) search

Approach 1: Recursive DFS (Recommended)

★ Recommended

Use a Trie for storage. For each search:

• If we encounter an exact letter, move to that child.
• If we encounter ’.’, recursively try all 26 children.
• Base case: reached end of word → check if it’s marked as end-of-word.

⏱ Time O(n×26^m) Worst-case backtracking 💾 Space O(m×26) Trie nodes

Pseudocode

class WordDictionary:
    root = TrieNode()

    function addWord(word):
        node = root
        for each char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    function search(word):
        return searchDFS(word, 0, root)

    function searchDFS(word, index, node):
        if index == len(word):
            return node.is_end_of_word

        char = word[index]
        if char == '.':
            for each child in node.children.values():
                if searchDFS(word, index + 1, child):
                    return True
            return False
        else:
            if char not in node.children:
                return False
            return searchDFS(word, index + 1, node.children[char])

Solution Code

Python

design_search_words_recursive.py

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

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

    def _search_dfs(self, word: str, index: int, node: TrieNode) -> bool:
        if index == len(word):
            return node.is_end_of_word

        char = word[index]
        if char == '.':
            for child in node.children.values():
                if self._search_dfs(word, index + 1, child):
                    return True
            return False
        else:
            if char not in node.children:
                return False
            return self._search_dfs(word, index + 1, node.children[char])


# Example usage
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

C++

design_search_words_recursive.cpp

#include <iostream>
#include <unordered_map>
#include <string>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool is_end_of_word = false;
};

class WordDictionary {
private:
    TrieNode* root;

    bool searchDFS(const std::string& word, int index, TrieNode* node) {
        if (index == (int)word.length()) {
            return node->is_end_of_word;
        }

        char ch = word[index];
        if (ch == '.') {
            for (auto& [c, child] : node->children) {
                if (searchDFS(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            return searchDFS(word, index + 1, node->children[ch]);
        }
    }

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

    void addWord(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->is_end_of_word = true;
    }

    bool search(const std::string& word) {
        return searchDFS(word, 0, root);
    }
};

int main() {
    WordDictionary wd;
    wd.addWord("bad");
    wd.addWord("dad");
    wd.addWord("mad");
    std::cout << wd.search("pad") << std::endl;  // 0
    std::cout << wd.search("bad") << std::endl;  // 1
    std::cout << wd.search(".ad") << std::endl;  // 1
    std::cout << wd.search("b..") << std::endl;  // 1
    return 0;
}

Java

DesignSearchWords_Recursive.java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class WordDictionary {
    private TrieNode root;

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

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

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

    private boolean searchDFS(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isEndOfWord;
        }

        char ch = word.charAt(index);
        if (ch == '.') {
            for (TrieNode child : node.children.values()) {
                if (searchDFS(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            return searchDFS(word, index + 1, node.children.get(ch));
        }
    }
}

public class DesignSearchWords_Recursive {
    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));  // false
        System.out.println(wd.search("bad"));  // true
        System.out.println(wd.search(".ad"));  // true
        System.out.println(wd.search("b.."));  // true
    }
}

JavaScript

design_search_words_recursive.js

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word) {
        let node = this.root;
        for (let char of word) {
            if (!(char in node.children)) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        return this.searchDFS(word, 0, this.root);
    }

    searchDFS(word, index, node) {
        if (index === word.length) {
            return node.isEndOfWord;
        }

        let char = word[index];
        if (char === '.') {
            for (let child of Object.values(node.children)) {
                if (this.searchDFS(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            if (!(char in node.children)) {
                return false;
            }
            return this.searchDFS(word, index + 1, node.children[char]);
        }
    }
}

// Example usage
const wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
console.log(wd.search("pad"));  // false
console.log(wd.search("bad"));  // true
console.log(wd.search(".ad"));  // true
console.log(wd.search("b.."));  // true

Rust

design_search_words_recursive.rs

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    is_end_of_word: bool,
}

struct WordDictionary {
    root: Rc<RefCell<TrieNode>>,
}

impl WordDictionary {
    fn new() -> Self {
        WordDictionary {
            root: Rc::new(RefCell::new(TrieNode::default())),
        }
    }

    fn add_word(&self, word: String) {
        let mut node = Rc::clone(&self.root);
        for ch in word.chars() {
            let mut node_ref = node.borrow_mut();
            node = Rc::clone(
                node_ref
                    .children
                    .entry(ch)
                    .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
            );
        }
        node.borrow_mut().is_end_of_word = true;
    }

    fn search(&self, word: String) -> bool {
        self.search_dfs(&word, 0, Rc::clone(&self.root))
    }

    fn search_dfs(&self, word: &str, index: usize, node: Rc<RefCell<TrieNode>>) -> bool {
        if index == word.len() {
            return node.borrow().is_end_of_word;
        }

        let chars: Vec<char> = word.chars().collect();
        let ch = chars[index];

        if ch == '.' {
            let node_ref = node.borrow();
            for child in node_ref.children.values() {
                if self.search_dfs(word, index + 1, Rc::clone(child)) {
                    return true;
                }
            }
            false
        } else {
            let node_ref = node.borrow();
            if let Some(child) = node_ref.children.get(&ch) {
                self.search_dfs(word, index + 1, Rc::clone(child))
            } else {
                false
            }
        }
    }
}

fn main() {
    let wd = WordDictionary::new();
    wd.add_word("bad".to_string());
    wd.add_word("dad".to_string());
    wd.add_word("mad".to_string());
    println!("{}", wd.search("pad".to_string()));  // false
    println!("{}", wd.search("bad".to_string()));  // true
    println!("{}", wd.search(".ad".to_string()));  // true
    println!("{}", wd.search("b..".to_string()));  // true
}

Go

design_search_words_recursive.go

package main

import "fmt"

type TrieNode struct {
  children    map[rune]*TrieNode
  isEndOfWord bool
}

type WordDictionary struct {
  root *TrieNode
}

func NewWordDictionary() *WordDictionary {
  return &WordDictionary{
    root: &TrieNode{
      children: make(map[rune]*TrieNode),
    },
  }
}

func (wd *WordDictionary) AddWord(word string) {
  node := wd.root
  for _, ch := range word {
    if _, exists := node.children[ch]; !exists {
      node.children[ch] = &TrieNode{
        children: make(map[rune]*TrieNode),
      }
    }
    node = node.children[ch]
  }
  node.isEndOfWord = true
}

func (wd *WordDictionary) Search(word string) bool {
  return wd.searchDFS(word, 0, wd.root)
}

func (wd *WordDictionary) searchDFS(word string, index int, node *TrieNode) bool {
  if index == len(word) {
    return node.isEndOfWord
  }

  ch := rune(word[index])
  if ch == '.' {
    for _, child := range node.children {
      if wd.searchDFS(word, index+1, child) {
        return true
      }
    }
    return false
  } else {
    if child, exists := node.children[ch]; exists {
      return wd.searchDFS(word, index+1, child)
    }
    return false
  }
}

func main() {
  wd := NewWordDictionary()
  wd.AddWord("bad")
  wd.AddWord("dad")
  wd.AddWord("mad")
  fmt.Println(wd.Search("pad"))  // false
  fmt.Println(wd.Search("bad"))  // true
  fmt.Println(wd.Search(".ad"))  // true
  fmt.Println(wd.Search("b.."))  // true
}

Approach 2: Iterative BFS

🎯 Interview Favourite

Maintain a queue of (node, index) pairs. For each step:

• If exact character, add (child_node, index+1) to queue.
• If ’.’, add all children with (child_node, index+1).
• Base case: reach end of word and check end-of-word flag.

⏱ Time O(n×26^m) Worst-case all branches 💾 Space O(m) Queue size

Solution Code

Python

design_search_words_iterative.py

from collections import deque


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

    def search(self, word: str) -> bool:
        queue = deque([(self.root, 0)])

        while queue:
            node, index = queue.popleft()

            if index == len(word):
                if node.is_end_of_word:
                    return True
                continue

            char = word[index]
            if char == '.':
                for child in node.children.values():
                    queue.append((child, index + 1))
            else:
                if char in node.children:
                    queue.append((node.children[char], index + 1))

        return False


# Example usage
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")
print(wd.search("pad"))  # False
print(wd.search("bad"))  # True
print(wd.search(".ad"))  # True
print(wd.search("b.."))  # True

C++

design_search_words_iterative.cpp

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool is_end_of_word = false;
};

class WordDictionary {
private:
    TrieNode* root;

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

    void addWord(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->is_end_of_word = true;
    }

    bool search(const std::string& word) {
        std::queue<std::pair<TrieNode*, int>> q;
        q.push({root, 0});

        while (!q.empty()) {
            auto [node, index] = q.front();
            q.pop();

            if (index == (int)word.length()) {
                if (node->is_end_of_word) {
                    return true;
                }
                continue;
            }

            char ch = word[index];
            if (ch == '.') {
                for (auto& [c, child] : node->children) {
                    q.push({child, index + 1});
                }
            } else {
                if (node->children.find(ch) != node->children.end()) {
                    q.push({node->children[ch], index + 1});
                }
            }
        }
        return false;
    }
};

int main() {
    WordDictionary wd;
    wd.addWord("bad");
    wd.addWord("dad");
    wd.addWord("mad");
    std::cout << wd.search("pad") << std::endl;  // 0
    std::cout << wd.search("bad") << std::endl;  // 1
    std::cout << wd.search(".ad") << std::endl;  // 1
    std::cout << wd.search("b..") << std::endl;  // 1
    return 0;
}

Java

DesignSearchWords_Iterative.java

import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.LinkedList;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class WordDictionary {
    private TrieNode root;

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

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

    public boolean search(String word) {
        Queue<Map.Entry<TrieNode, Integer>> queue = new LinkedList<>();
        queue.offer(new java.util.AbstractMap.SimpleEntry<>(root, 0));

        while (!queue.isEmpty()) {
            Map.Entry<TrieNode, Integer> entry = queue.poll();
            TrieNode node = entry.getKey();
            int index = entry.getValue();

            if (index == word.length()) {
                if (node.isEndOfWord) {
                    return true;
                }
                continue;
            }

            char ch = word.charAt(index);
            if (ch == '.') {
                for (TrieNode child : node.children.values()) {
                    queue.offer(new java.util.AbstractMap.SimpleEntry<>(child, index + 1));
                }
            } else {
                if (node.children.containsKey(ch)) {
                    queue.offer(new java.util.AbstractMap.SimpleEntry<>(node.children.get(ch), index + 1));
                }
            }
        }
        return false;
    }
}

public class DesignSearchWords_Iterative {
    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        System.out.println(wd.search("pad"));  // false
        System.out.println(wd.search("bad"));  // true
        System.out.println(wd.search(".ad"));  // true
        System.out.println(wd.search("b.."));  // true
    }
}

JavaScript

design_search_words_iterative.js

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word) {
        let node = this.root;
        for (let char of word) {
            if (!(char in node.children)) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        const queue = [[this.root, 0]];

        while (queue.length > 0) {
            const [node, index] = queue.shift();

            if (index === word.length) {
                if (node.isEndOfWord) {
                    return true;
                }
                continue;
            }

            let char = word[index];
            if (char === '.') {
                for (let child of Object.values(node.children)) {
                    queue.push([child, index + 1]);
                }
            } else {
                if (char in node.children) {
                    queue.push([node.children[char], index + 1]);
                }
            }
        }
        return false;
    }
}

// Example usage
const wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
console.log(wd.search("pad"));  // false
console.log(wd.search("bad"));  // true
console.log(wd.search(".ad"));  // true
console.log(wd.search("b.."));  // true

Rust

design_search_words_iterative.rs

use std::collections::{HashMap, VecDeque};
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, Rc<RefCell<TrieNode>>>,
    is_end_of_word: bool,
}

struct WordDictionary {
    root: Rc<RefCell<TrieNode>>,
}

impl WordDictionary {
    fn new() -> Self {
        WordDictionary {
            root: Rc::new(RefCell::new(TrieNode::default())),
        }
    }

    fn add_word(&self, word: String) {
        let mut node = Rc::clone(&self.root);
        for ch in word.chars() {
            let mut node_ref = node.borrow_mut();
            node = Rc::clone(
                node_ref
                    .children
                    .entry(ch)
                    .or_insert_with(|| Rc::new(RefCell::new(TrieNode::default()))),
            );
        }
        node.borrow_mut().is_end_of_word = true;
    }

    fn search(&self, word: String) -> bool {
        let mut queue: VecDeque<(Rc<RefCell<TrieNode>>, usize)> =
            VecDeque::new();
        queue.push_back((Rc::clone(&self.root), 0));

        let chars: Vec<char> = word.chars().collect();

        while let Some((node, index)) = queue.pop_front() {
            if index == word.len() {
                if node.borrow().is_end_of_word {
                    return true;
                }
                continue;
            }

            let ch = chars[index];
            if ch == '.' {
                let node_ref = node.borrow();
                for child in node_ref.children.values() {
                    queue.push_back((Rc::clone(child), index + 1));
                }
            } else {
                let node_ref = node.borrow();
                if let Some(child) = node_ref.children.get(&ch) {
                    queue.push_back((Rc::clone(child), index + 1));
                }
            }
        }
        false
    }
}

fn main() {
    let wd = WordDictionary::new();
    wd.add_word("bad".to_string());
    wd.add_word("dad".to_string());
    wd.add_word("mad".to_string());
    println!("{}", wd.search("pad".to_string()));  // false
    println!("{}", wd.search("bad".to_string()));  // true
    println!("{}", wd.search(".ad".to_string()));  // true
    println!("{}", wd.search("b..".to_string()));  // true
}

Go

design_search_words_iterative.go

package main

import "fmt"

type TrieNode struct {
  children    map[rune]*TrieNode
  isEndOfWord bool
}

type WordDictionary struct {
  root *TrieNode
}

func NewWordDictionary() *WordDictionary {
  return &WordDictionary{
    root: &TrieNode{
      children: make(map[rune]*TrieNode),
    },
  }
}

func (wd *WordDictionary) AddWord(word string) {
  node := wd.root
  for _, ch := range word {
    if _, exists := node.children[ch]; !exists {
      node.children[ch] = &TrieNode{
        children: make(map[rune]*TrieNode),
      }
    }
    node = node.children[ch]
  }
  node.isEndOfWord = true
}

func (wd *WordDictionary) Search(word string) bool {
  type state struct {
    node  *TrieNode
    index int
  }

  queue := []state{{wd.root, 0}}

  for len(queue) > 0 {
    current := queue[0]
    queue = queue[1:]

    if current.index == len(word) {
      if current.node.isEndOfWord {
        return true
      }
      continue
    }

    ch := rune(word[current.index])
    if ch == '.' {
      for _, child := range current.node.children {
        queue = append(queue, state{child, current.index + 1})
      }
    } else {
      if child, exists := current.node.children[ch]; exists {
        queue = append(queue, state{child, current.index + 1})
      }
    }
  }
  return false
}

func main() {
  wd := NewWordDictionary()
  wd.AddWord("bad")
  wd.AddWord("dad")
  wd.AddWord("mad")
  fmt.Println(wd.Search("pad"))  // false
  fmt.Println(wd.Search("bad"))  // true
  fmt.Println(wd.Search(".ad"))  // true
  fmt.Println(wd.Search("b.."))  // true
}

Common mistakes

Watch for these pitfalls

• Treating ’.’ as a regular character instead of exploring all branches.
• Returning early without checking all wildcard possibilities.
• Forgetting to mark nodes as end-of-word during insertion.
• In iterative approach, queue explosion with many wildcards — this is unavoidable in worst case.
• Not handling the base case correctly (index == word length).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

design_add_and_search_words_data_structure_space_optimized.py

"""
Solution for Design Add and Search Words Data Structure
"""

def solve():
    """Implementation for approach 3 of Design Add and Search Words Data Structure"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

design_add_and_search_words_data_structure_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Design Add and Search Words Data Structure
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

DesignAddAndSearchWordsDataStructureSpaceOptimized.java

/**
 * Solution for Design Add and Search Words Data Structure
 * Approach 3
 */
public class DesignAddAndSearchWordsDataStructureSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

design_add_and_search_words_data_structure_space_optimized.js

/**
 * Solution for Design Add and Search Words Data Structure
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

design_add_and_search_words_data_structure_space_optimized.rs

/// Solution for Design Add and Search Words Data Structure
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

design_add_and_search_words_data_structure_space_optimized.go

package main

import "fmt"

// Solution for Design Add and Search Words Data Structure
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Implement Trie (Prefix Tree) ↗ Medium #208
• Word Search II ↗ Hard #212
• Word Search ↗ Medium #79

Interview Tips

Key trade-offs to discuss

• Recursive vs. Iterative: Recursive is cleaner and more intuitive for wildcards; iterative avoids stack overhead.
• When ’.’ is expensive: With many wildcards, search becomes exponential. Discuss memoization or limiting wildcard count.
• Space-time tradeoff: Trie takes more space upfront but makes adds/searches fast.
• Follow-up: How would you optimize for many ’.’ searches? (Use memoization with (index, node) cache.)
• Edge cases: Single ’.’ matching single character, all dots, no matches, duplicate adds.

← Previous
#210 Course Schedule III Next
#212 Word Search II →