Design Add and Search Words Data Structure

Difficulty: Medium

Design a data structure that stores words and can search for them, but with a twist: a search query may contain . characters, and each . can match any single letter.

Build a class with two operations:

  • addWord(word) - adds a word to the structure.
  • search(word) - returns true if there's a stored word that matches the query, where . in the query can stand in for any one letter. The query is always matched against stored words of the same length.

Examples

Input: addWord("bad"); addWord("dad"); addWord("mad"); search("pad"); search("bad"); search(".ad"); search("b..")
Output: false, true, true, true

"pad" was never added, so it fails. "bad" matches exactly. ".ad" matches "bad", "dad", or "mad" since "." covers the first letter. "b.." matches "bad" - "." covers the 2nd and 3rd letters.

Input: addWord("a"); search(".")
Output: true

A single "." matches any single-letter word, including "a".

Constraints

  • 1 <= word.length <= 25

  • word in addWord consists of lowercase English letters

  • word in search consists of lowercase English letters and/or '.'

  • At most 2 * 10^4 calls total to addWord and search

Approach

Store words in a trie exactly like the plain prefix-tree problem - each node has children keyed by letter and a flag for word-endings. The only change is in how search walks the tree: a regular letter still follows exactly one child, but a . means "try every child this node has" and succeed if any of them leads to a full match on the rest of the query.

That "try every possibility, succeed if one works" is a small backtracking search layered on top of the trie structure, so search becomes a recursive helper that takes the current trie node and how far into the query string it's gotten.

Solutions

Brute Force - Array of Words

Keep every added word in a plain array. For search, compare the query against every stored word of the same length, treating '.' as a wildcard for that one position.

class WordDictionary {
  constructor() {
    this.words = [];
  }

  addWord(word) {
    this.words.push(word);
  }

  search(word) {
    for (const stored of this.words) {
      if (stored.length !== word.length) continue;
      let matches = true;
      for (let i = 0; i < word.length; i++) {
        if (word[i] !== "." && word[i] !== stored[i]) {
          matches = false;
          break;
        }
      }
      if (matches) return true;
    }
    return false;
  }
}

Time: O(1) for addWord; O(n * L) for search, where n is stored word count and L is word length · Space: O(n * L) to store all words

Optimal - Trie with Wildcard Backtracking

Store words in a trie as usual. To search, recursively walk the query: a normal letter follows exactly one child; a '.' tries every child of the current node and succeeds if any of them lets the rest of the query match.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = 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.isWord = true;
  }

  search(word) {
    // Recursively tries to match word[i..] starting at trie node `node`.
    const dfs = (node, i) => {
      if (node === null) return false;
      if (i === word.length) return node.isWord;

      const ch = word[i];
      if (ch === ".") {
        for (const child of node.children.values()) {
          if (dfs(child, i + 1)) return true;
        }
        return false;
      }

      return dfs(node.children.get(ch) ?? null, i + 1);
    };

    return dfs(this.root, 0);
  }
}

Time: O(L) for addWord. For search, O(L) in the average case, worst case O(26^L) when the query is all dots and every node is fully branching · Space: O(N) total for the trie's stored letters, plus O(L) recursion depth per search