Implement Trie search with wildcard matching
Company: Trexquant
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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++.
Quick Answer: This question evaluates understanding of trie data structures, string pattern matching with wildcard characters, and efficient algorithm design for large-scale add/search operations.
Process operations ["add", word] and ["search", pattern]. In search, . matches exactly one lowercase letter. Return all search booleans.
Constraints
- Words are lowercase English strings
Examples
Input: ([['add', 'bad'], ['add', 'dad'], ['add', 'mad'], ['search', 'pad'], ['search', 'bad'], ['search', '.ad'], ['search', 'b..']],)
Expected Output: [False, True, True, True]
Input: ([['search', '.'], ['add', 'a'], ['search', '.'], ['search', '..']],)
Expected Output: [False, True, False]
Hints
- DFS branches only when the pattern character is a wildcard.