Skip to main content

211. Design Add and Search Words Data Structure

mediumAsked at Amazon

Implement a dictionary supporting addWord and search where '.' is a wildcard. Amazon asks this to test whether you reach for a trie and can handle the wildcard via DFS over all children.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a trie extension question.
  • Blind (2025-10)— Recurring Amazon interview problem.

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: addWord adds word to the data structure; search returns true if there is any string in the data structure that matches word. 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('bad'); addWord('dad'); addWord('mad'); search('pad'); search('bad'); search('.ad'); search('b..')
Output
[null,null,null,null,false,true,true,true]

Approaches

1. Trie with DFS for wildcard (optimal)

Standard trie. search recurses: for normal chars, descend to that child. For '.', recurse into every child.

Time
O(L) addWord, O(L * 26^D) search (D = dot count)
Space
O(N * L)
class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class WordDictionary {
  constructor() {
    this.root = new TrieNode();
  }
  addWord(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(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 node.children.values()) {
          if (dfs(child, i + 1)) return true;
        }
        return false;
      }
      if (!node.children.has(ch)) return false;
      return dfs(node.children.get(ch), i + 1);
    }
    return dfs(this.root, 0);
  }
}

Tradeoff: Trie + DFS handles wildcards naturally. The branching factor on '.' is bounded by 26 (the alphabet) — and the constraint bounds dots to 2, so worst case is 26^2 = 676 paths per search.

Amazon-specific tips

Amazon interviewers grade this on whether you handle the wildcard branching. State out loud: 'A trie gives me prefix matching naturally. For wildcards, I DFS into every child at that position — at most 26 branches.' The branching factor matters; the dot-count constraint keeps worst-case bounded.

Common mistakes

  • Iterating wildcard branches sequentially without short-circuiting on first match.
  • Forgetting that '.' at the END of word still requires isEnd === true on some child.
  • Storing words in a flat list and scanning — O(N*L) per search, fails the spec at scale.

Follow-up questions

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

  • What if wildcards could match multiple chars (LC 44 - Wildcard Matching)?
  • What if the dictionary supported deletion?
  • What if the alphabet were huge?

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 instead of a flat list?

Trie shares common prefixes across words. With 10^4 words averaging 25 chars, that's significant memory savings. Plus, prefix-based wildcard search becomes natural via DFS.

Can the wildcard match an empty string?

No — '.' must match exactly one character. The DFS only advances i when consuming one position.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →