Coding questions · Trexquant

Implement Trie search with wildcard matching

This question evaluates understanding of trie data structures, string pattern matching with wildcard characters, and efficient algorithm design for large-scale add/search operations.

Design a text dictionary using a Trie.

Support the following operations:

addWord(word): Insert a lowercase English word.
search(pattern): Return true if any previously added word matches pattern.

The pattern may contain the wildcard character . which matches exactly one lowercase letter. (All other characters match themselves.)

Inputs/Outputs

You may implement a class with these two methods, or write functions that process a sequence of operations.

Constraints

Number of operations up to ~10^5.
Word/pattern length up to ~10^3 (assume typical interview constraints; optimize beyond naive scanning).
Must be implemented in C++.

Trie Search with Wildcards

Examples

Example 1

Input: ([['add', 'bad'], ['add', 'dad'], ['add', 'mad'], ['search', 'pad'], ['search', 'bad'], ['search', '.ad'], ['search', 'b..']],)
Output: [False, True, True, True]

Example 2

Input: ([['search', '.'], ['add', 'a'], ['search', '.'], ['search', '..']],)
Output: [False, True, False]

Hints

DFS branches only when the pattern character is a wildcard.