Add and Search Word

Designing a data structure that supports both exact and wildcard searches is crucial in auto-complete, spell-checkers, and dictionary lookups. The “Add and Search Word” problem tests your ability to choose and traverse a trie (prefix tree) with backtracking for patterns.

Problem Statement

Implement a data structure WordDictionary with two operations:

• void addWord(String word): Inserts word into the data structure.

• boolean search(String word): Returns true if there is any previously added string that matches word, allowing '.' to match any single letter. Otherwise, returns false.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") → false
search("bad") → true
search(".ad") → true
search("b..") → true

1. Clarify Requirements Before Jumping Into Code

I want to be precise:

• Words are lowercase a–z only.

• The wildcard '.' matches exactly one letter.

• addWord and search must both work efficiently for many calls.

• Expect up to thousands of words and searches.

• search should handle patterns of any length.

2. Identify the Category of the Question

This is a trie + backtracking question, a data-structure-design pattern. Common patterns:

• Standard trie for prefix lookups in O(L).

• DFS/backtracking on trie when wildcards require exploring multiple branches.

• End-of-word markers in trie nodes to signal full-word matches.

3. Consider a Brute-Force Approach to Understand the Problem

For a brute-force solution, my first thought is to simply store all words in a list.

• addWord can be done in O(1) time by simply appending to the list.

• search: iterate through the list and compare each string, character by character, allowing '.' as a match for any character. That's O(N * L) time.

Where N = number of words, L = pattern length.

This works, but can we do better?

4. Brainstorm More Solutions

I need to find a way to improve my search speed. I could consider an optimization like filtering out words that are longer than my target string. But in the worst case, that doesn't actually help. I could still end up with O(N * L) time.

Many of our standard storage data structures are going to run into the same problem - forcing me to do character by character comparisons. So it seems I need a more specialized data structure. Luckily, we know there is one data structure that excels when it comes to searching strings, especially when we have requirements like prefix-matching or partial-matching. A trie!

So, how do I apply a trie to this problem? If I ignore the wildcard requirement, then this becomes a simple trie implementation problem. We can insert and search exact words in O(L) time.

But the wildcard requirement complicates the solution. If I'm comparing against a known character, then I simply follow that character to its child. But when I hit a wildcard, all of a sudden I have a whole tree's worth of characters to compare.

So then the question becomes, how do I efficiently search a tree? We go to our standard algorithms for tree traversal: Breadth-First-Search (BFS) and Depth-First-Search (DFS)!

How do we choose which one? In this case, it doesn't really matter, since we end up needing to check all paths either way.

The runtime for Trie + DFS can be quite terrible: O(26^W) for W wildcards. But that's probably not gonna happen much in real life, so we'll go with it.

5. Discuss Trade-Offs Between Your Solutions

Approach	addWord	search	Space	Pros	Cons
List + linear scan	O(1)	O(N·L)	O(N·L)	Easy to implement	Too slow for many searches
Trie (exact only)	O(L)	O(L)	O(N·L)	Fast exact, prefix queries	Cannot handle wildcards directly
Trie + DFS backtracking	O(L)	O(branches)	O(N·L)	Handles wildcards and exact	DFS branching can explode in worst case

6. Write Pseudocode to Structure Your Thoughts

class TrieNode:
  children[26]
  isWord

function addWord(word):
  node = root
  for c in word:
    i = c - 'a'
    if node.children[i] is null:
      node.children[i] = new TrieNode()
    node = node.children[i]
  node.isWord = true

function search(node, word, idx):
  if idx == word.length:
    return node.isWord
  c = word[idx]
  if c != '.':
    child = node.children[c - 'a']
    return child != null and search(child, word, idx+1)
  else:
    for each child in node.children:
      if child != null and search(child, word, idx+1):
        return true
    return false

7. Consider Edge Cases

• Searching an empty word → only true if we inserted "".

• Words of differing lengths → early return false if trie path ends early.

• Patterns of all wildcards → must explore entire trie at each level.

• No words added → all searches return false.

8. Write Full Code Syntax

class WordDictionary {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    private final TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                node.children[i] = new TrieNode();
            }
            node = node.children[i];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return dfsSearch(root, word, 0);
    }

    private boolean dfsSearch(TrieNode node, String word, int idx) {
        if (idx == word.length()) {
            return node.isWord;
        }
        char c = word.charAt(idx);
        if (c != '.') {
            TrieNode child = node.children[c - 'a'];
            return child != null && dfsSearch(child, word, idx + 1);
        }
        for (TrieNode child : node.children) {
            if (child != null && dfsSearch(child, word, idx + 1)) {
                return true;
            }
        }
        return false;
    }
}

9. Test Your Code

public static void main(String[] args) {
    WordDictionary dict = new WordDictionary();

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

    System.out.println(!dict.search("pad"));  // false
    System.out.println(dict.search("bad"));   // true
    System.out.println(dict.search(".ad"));   // true
    System.out.println(dict.search("b.."));   // true

    System.out.println(!dict.search("...s")); // false
    dict.addWord("");
    System.out.println(dict.search(""));      // true
}

10. Key Lessons to Remember for Future Questions

• A trie supports fast prefix- and exact-word operations in O(L).

• Marking end-of-word flags is essential for distinguishing prefixes from full words.

• Worst-case wildcard patterns may explore many branches, so be mindful of the constraints given in your problem statement!

Good Luck and Happy Coding!