Katkat
Back

Implement Trie search with wildcard matching

TrexquantSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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++.