Skip to main content

211. Design Add and Search Words Data Structure

mediumAsked at Apple

Design Add and Search Words Data Structure is Apple's go-to trie design medium. Add inserts a word normally; search supports '.' as a wildcard that matches any single character. The wildcard turns the search into a tiny DFS down every matching child node.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list this as a recurring 30-minute trie design medium.
  • Blind (2025-12)— Apple ICT3/ICT4 reports cite Design Add and Search Words as the canonical wildcard-search question.

Problem

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.

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 2 dots in word for search queries.
  • At most 10^4 calls will be made to addWord and search.

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]

Approaches

1. Trie + DFS search with wildcard handling (optimal)

Standard trie add. For search, recurse from a node and current index: if char is '.', try EVERY child; else descend the matching child.

Time
O(m) addWord, O(26^k * m) search where k is number of dots
Space
O(total chars added)
class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class WordDictionary {
  constructor() { this.root = new TrieNode(); }
  addWord(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  search(word) {
    function dfs(node, i) {
      if (i === word.length) return node.isEnd;
      const ch = word[i];
      if (ch === '.') {
        for (const child of Object.values(node.children)) {
          if (dfs(child, i + 1)) return true;
        }
        return false;
      }
      const next = node.children[ch];
      if (!next) return false;
      return dfs(next, i + 1);
    }
    return dfs(this.root, 0);
  }
}

Tradeoff: Add is O(m). Search is O(m) for no dots, branching factor up to 26 per dot. The constraint of at most 2 dots keeps the explosion bounded. Apple's preferred answer because the trie generalizes to other prefix problems.

2. Hash set + linear filter (rejected)

Store all words in a set. For search with dots, scan every stored word for length and pattern match.

Time
O(1) addWord, O(n * m) search
Space
O(total chars)
class WordDictionary {
  constructor() { this.words = new Set(); }
  addWord(word) { this.words.add(word); }
  search(word) {
    for (const w of this.words) {
      if (w.length !== word.length) continue;
      let ok = true;
      for (let i = 0; i < w.length; i++) {
        if (word[i] !== '.' && word[i] !== w[i]) { ok = false; break; }
      }
      if (ok) return true;
    }
    return false;
  }
}

Tradeoff: O(n) per search where n is total words. Times out at the upper-bound constraints. Apple reject reason: 'you're not exploiting the prefix structure.'

Apple-specific tips

Apple's grade on this is whether the search DFS handles BOTH cases (letter and dot) cleanly. Say: 'for a regular letter, descend the matching child. For a dot, try every child — return true if any subtree matches.' That phrasing maps directly to the code. The 'at most 2 dots' constraint is what keeps the branching reasonable; mention it.

Common mistakes

  • Forgetting the i === word.length base case must check isEnd, not just return true.
  • Iterating over child keys instead of values — works but does an extra lookup per child.
  • Forgetting that '.' should match any letter even at the LAST position of the word (still need isEnd on that child).

Follow-up questions

An interviewer at Apple may pivot to one of these next:

  • Implement Trie (LC 208) — the warm-up.
  • Word Search II (LC 212) — trie + grid DFS.
  • What if there could be UNBOUNDED wildcards? The branching becomes exponential — switch to BFS or memoize states.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why a trie and not a hash set?

The trie exploits the prefix structure: dots can prune entire subtrees in one step. A hash set has to look at every stored word individually.

Worst case for search?

With k dots, up to 26^k branches per dot. For k=2 that's 676 per word — fine. For arbitrary k it would be exponential.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Design Add and Search Words Data Structure and other Apple interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →