Skip to main content

86. Design Add and Search Words Data Structure

mediumAsked at Datadog

Design a dictionary with addWord and search where '.' matches any letter. Datadog uses this for the Trie + DFS combo — same shape as their wildcard-tag-pattern lookup in the metric query layer.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — wildcard-tag-pattern analog.

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class with addWord(word) and search(word). search(word) 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 consists of lowercase English letters and '.' characters.
  • At most 10^4 calls.

Examples

Example 1

Input
addWord('bad'), addWord('dad'), addWord('mad'), search('pad'), search('bad'), search('.ad'), search('b..')
Output
[null,null,null,false,true,true,true]

Approaches

1. List of words + regex match

Store all words; on search, regex match each.

Time
search O(N * L)
Space
O(total chars)
// Store list; on search, for each word, check matches with the pattern.

Tradeoff: O(N*L) per search — Datadog will push for Trie.

2. Trie + DFS for wildcards (optimal)

Insert into Trie as usual. On search with '.', recurse on ALL children at that level.

Time
addWord O(L), search O(L) avg / O(26^L) worst
Space
O(total chars)
class WordDictionary {
  constructor() { this.root = { children: new Map(), isEnd: false }; }
  addWord(word) {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, { children: new Map(), isEnd: false });
      n = n.children.get(c);
    }
    n.isEnd = true;
  }
  search(word) {
    function dfs(node, i) {
      if (i === word.length) return node.isEnd;
      const c = word[i];
      if (c === '.') {
        for (const child of node.children.values()) if (dfs(child, i + 1)) return true;
        return false;
      }
      if (!node.children.has(c)) return false;
      return dfs(node.children.get(c), i + 1);
    }
    return dfs(this.root, 0);
  }
}

Tradeoff: Trie + DFS branches on '.'. Worst case 26^L if all chars are '.' but practical cases are fast. Datadog-canonical wildcard query.

Datadog-specific tips

Datadog will probe with: 'How many '.'s before this gets slow?' Worst-case 26^L for all-wildcards; in practice constrained by ~25 chars. Articulate why this is acceptable: most searches have few wildcards.

Common mistakes

  • Iterating Map.entries instead of Map.values for '.' branching — the keys aren't needed.
  • Forgetting node.isEnd check on the last character — returns true for prefixes.
  • Recursing on Set instead of Map — Set doesn't preserve mapping.

Follow-up questions

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

  • Implement Trie (LC 208) — base case.
  • Word Search II (LC 212) — Trie + DFS on a board.
  • Datadog-style: wildcard pattern over tag space.

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 DFS at '.'?

The wildcard could match any child. We must explore all branches to know if ANY leads to a valid completion.

Worst-case complexity?

If the search is all '.' (e.g. '....'), we explore every node up to depth L — that's O(26^L) in the worst case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →