Skip to main content

211. Design Add and Search Words Data Structure

mediumAsked at Airbnb

Design WordDictionary with addWord and a search that supports '.' as any-char. Airbnb asks this to test trie + bounded DFS — '.' branches all 26 children at that position.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb L4 onsite reports list this as a recurring trie-design medium.
  • Blind (2025-12)— Recurring in Airbnb backend interview reports.

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

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. Trie + DFS for '.' (optimal)

Build a trie on addWord. On search, DFS the trie; on '.', recurse into all current children.

Time
O(L) for addWord; O(26^d * L) for search with d dots
Space
O(total chars)
class WordDictionary {
  constructor() { this.root = {}; }
  addWord(word) {
    let node = this.root;
    for (const c of word) {
      if (!node[c]) node[c] = {};
      node = node[c];
    }
    node.isEnd = true;
  }
  search(word) {
    function dfs(node, i) {
      if (i === word.length) return !!node.isEnd;
      const c = word[i];
      if (c === '.') {
        for (const k in node) {
          if (k === 'isEnd') continue;
          if (dfs(node[k], i + 1)) return true;
        }
        return false;
      }
      if (!node[c]) return false;
      return dfs(node[c], i + 1);
    }
    return dfs(this.root, 0);
  }
}

Tradeoff: Trie gives O(L) per add. Search branches up to 26 children per '.'. With the at-most-3-dots constraint, search is effectively O(L * 26^3) worst case.

2. Per-length hash set (alternative)

Group words by length. For a query of length L, walk the group for length L and check char-by-char.

Time
O(W_L * L) per search
Space
O(total chars)
class WordDictionaryByLen {
  constructor() { this.byLen = new Map(); }
  addWord(word) {
    if (!this.byLen.has(word.length)) this.byLen.set(word.length, new Set());
    this.byLen.get(word.length).add(word);
  }
  search(word) {
    const bucket = this.byLen.get(word.length);
    if (!bucket) return false;
    if (!word.includes('.')) return bucket.has(word);
    for (const w of bucket) {
      let ok = true;
      for (let i = 0; i < word.length; i++) {
        if (word[i] !== '.' && word[i] !== w[i]) { ok = false; break; }
      }
      if (ok) return true;
    }
    return false;
  }
}

Tradeoff: Simpler code but linear scan per length. Wins when there are few words; loses for dictionaries with many words of the same length.

Airbnb-specific tips

Airbnb wants the trie + DFS framing said out loud: 'Trie for O(L) insert. On search, the dot branches all current children — that's why search is exponential in the dot count.' Then mention the at-most-3-dots constraint to bound the cost. Coding without naming the dot fan-out is a flag.

Common mistakes

  • Using a 26-element array for children — fine in C++, JS objects are usually cleaner.
  • Forgetting isEnd — a search for a prefix that's never been added returns true.
  • On '.', not iterating over keys correctly (don't recurse into isEnd as a child).

Follow-up questions

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

  • Word Search II (LC 212) — same trie + grid DFS.
  • Stream of Characters (LC 1032) — reverse trie of suffixes.
  • Implement Trie / Prefix Tree (LC 208) — the basic version.

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 does '.' make search potentially exponential?

Each '.' can match any of up to 26 children, and each branch independently continues. With d dots, the worst case is 26^d branches.

When does the per-length variant win?

When the dictionary is small or queries rarely have dots. For dictionaries with many same-length words, trie + DFS wins.

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 Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →