Solving Design Add and Search Words in JavaScript: Step-by-Step Guide

The "Design Add and Search Words" problem is a classic data structure challenge that frequently appears in coding interviews and real-world search applications. It asks you to build a system that supports adding words and searching for them, with a twist: the search query may contain dots (.) that act as wildcards matching any single letter. In this tutorial, we'll break down the problem, explore the optimal Trie-based solution, and walk through a complete JavaScript implementation.

What Is the Problem?

The task is to design a data structure that supports two operations:

addWord(word) — Adds a word into the data structure.
search(word) — Returns true if any word in the structure matches the query. The query can contain the . character, which matches any single letter.

For example, after adding the words "bad", "dad", and "mad", a search for "pad" returns false, "bad" returns true, and ".ad" returns true because the dot matches b, d, or m.

Why It Matters

This problem matters because it teaches you how to combine two fundamental concepts: prefix trees (Tries) and backtracking. Tries are the backbone of autocomplete systems, spell checkers, and IP routing tables. Adding wildcard support forces you to think recursively, exploring multiple branches when a dot is encountered. Mastering this pattern prepares you for more advanced problems like word search puzzles, regex matching, and dictionary-based search engines.

In production systems, similar structures power features like fuzzy search, autocomplete suggestions, and contact list filtering. Understanding the trade-offs between time and space complexity here directly translates to building efficient search infrastructure.

Understanding the Trie Data Structure

A Trie (pronounced "try") is a tree-like data structure where each node represents a single character of a string. Words are stored by sharing common prefixes, which makes prefix-based lookups extremely efficient. Each node holds a map of child characters and a boolean flag indicating whether it marks the end of a valid word.

For the wildcard search, when we encounter a ., we must explore every possible child node at that level. This is where recursion and backtracking come into play — we try each branch and return true if any path leads to a complete word match.

Step-by-Step Implementation

Step 1: Define the Trie Node

Each node needs a dictionary to store its children and a flag to mark the end of a word. In JavaScript, we can use a plain object for the children map for simplicity and fast lookups.

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

Step 2: Build the WordDictionary Class

The WordDictionary class initializes with a root TrieNode. The addWord method walks down the tree, creating new nodes as needed, and marks the final node as the end of a word.

class WordDictionary {
  constructor() {
    this.root = new TrieNode();
  }

  addWord(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
}

Step 3: Implement Search With Wildcard Support

The search method is where the magic happens. We use a recursive helper function that takes the current node and the remaining portion of the word. For each character, if it's a letter, we follow that specific child. If it's a dot, we recursively try every child node and return true if any path succeeds.

class WordDictionary {
  constructor() {
    this.root = new TrieNode();
  }

  addWord(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    const dfs = (node, index) => {
      // Base case: reached the end of the word
      if (index === word.length) {
        return node.isEndOfWord;
      }

      const char = word[index];

      if (char === '.') {
        // Wildcard: try every possible child
        for (const key in node.children) {
          if (dfs(node.children[key], index + 1)) {
            return true;
          }
        }
        return false;
      } else {
        // Regular character: follow the specific child
        if (!node.children[char]) {
          return false;
        }
        return dfs(node.children[char], index + 1);
      }
    };

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

Step 4: Test the Implementation

Let's verify the solution with the example from the problem statement to make sure everything works as expected.

const dict = new WordDictionary();

dict.addWord("bad");
dict.addWord("dad");
dict.addWord("mad");

console.log(dict.search("pad"));   // false
console.log(dict.search("bad"));   // true
console.log(dict.search(".ad"));   // true
console.log(dict.search("b.."));   // true
console.log(dict.search("..."));   // true
console.log(dict.search("b.d"));   // true
console.log(dict.search("b..."));  // false (too long)

Complexity Analysis

For the addWord operation, the time complexity is O(L) where L is the length of the word, since we traverse one node per character. The space complexity per insertion is also O(L) in the worst case when no prefixes are shared.

For search, the best case (no wildcards) is O(L). However, when wildcards are present, the worst-case time complexity becomes O(26^L) because each dot could branch into up to 26 children. In practice, the branching is limited by the actual words stored, so performance is much better than the theoretical worst case.

Best Practices

Use Maps instead of plain objects if you need to avoid prototype pollution or want slightly better performance with frequent insertions and deletions. A Map avoids inherited properties like toString that plain objects carry.
Consider iterative addWord as shown above — it's simpler and faster than a recursive version for insertion since there's no branching.
Optimize for common queries by caching frequent search results if your application repeatedly searches the same patterns.
Handle edge cases early — empty strings, null inputs, and non-alphabetic characters should be validated before processing.
Use a fixed-size array for children if you only support lowercase English letters. An array of size 26 can be faster than a hash map due to direct indexing, though it uses more memory.
Consider memory cleanup if words can be deleted — implement a removeWord method that prunes unused branches to keep the Trie compact.

Alternative: Array-Based Trie Node

If you know the input only contains lowercase letters, you can optimize the node using a fixed-size array. This avoids hash map overhead and makes child access a constant-time array lookup.

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEndOfWord = false;
  }
}

class WordDictionary {
  constructor() {
    this.root = new TrieNode();
  }

  addWord(word) {
    let node = this.root;
    for (const char of word) {
      const index = char.charCodeAt(0) - 97; // 'a' is 97
      if (!node.children[index]) {
        node.children[index] = new TrieNode();
      }
      node = node.children[index];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    const dfs = (node, i) => {
      if (i === word.length) return node.isEndOfWord;

      const char = word[i];
      if (char === '.') {
        for (const child of node.children) {
          if (child && dfs(child, i + 1)) {
            return true;
          }
        }
        return false;
      } else {
        const index = char.charCodeAt(0) - 97;
        return node.children[index] ? dfs(node.children[index], i + 1) : false;
      }
    };

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

Common Pitfalls to Avoid

Forgetting the end-of-word flag — A common mistake is assuming that reaching a node means a word exists. You must check isEndOfWord because a node might just be a prefix of a longer word.
Not handling the empty string — Make sure your implementation correctly handles adding and searching for an empty string, which should match only if an empty string was explicitly added.
Inefficient wildcard handling — Avoid converting the Trie to a flat list of words and then filtering. That defeats the purpose of using a Trie and degrades performance significantly.
Stack overflow on deep recursion — For extremely long words, the recursive DFS could hit JavaScript's call stack limit. In such cases, consider an iterative approach using an explicit stack.

Conclusion

The "Design Add and Search Words" problem is a powerful exercise in combining Tries with recursive backtracking. By storing words in a prefix tree and exploring all possible branches when a wildcard appears, you achieve efficient lookups that scale well with real-world vocabulary sizes. The JavaScript implementation we built is clean, readable, and production-ready, with clear extension points for optimizations like array-based children or result caching. Whether you're preparing for interviews or building a search feature, mastering this pattern gives you a solid foundation for tackling more complex string-matching challenges. Practice variations like supporting multiple wildcards, adding deletion, or integrating fuzzy matching to deepen your understanding even further.