Katkat
Back

Solve prefix, array, and string problems

PinterestMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage prefix-based string searching using a Trie data structure, specifically focusing on handling wildcard character matching.

Problem: Trie with Wildcard Support

Design a data structure that supports storing a collection of strings and performing prefix searches that include a wildcard character. Implement the PrefixSearcher class:

  • void insert(String word): Inserts a string into the data structure.
  • boolean searchPrefix(String prefix): Returns true if any string currently in the structure starts with the given prefix. The prefix may contain the character '.', which acts as a wildcard capable of matching any single lowercase English letter.

Constraints

  • The total number of characters across all insert calls will not exceed 10^5.
  • The length of any prefix will not exceed 100.
  • Time complexity should be optimized to avoid iterating over all stored words during a search.

Examples

Example 1:

ps = PrefixSearcher()
ps.insert("apple")
ps.insert("apply")
print(ps.searchPrefix("app"))   # Output: True
print(ps.searchPrefix("a.p"))   # Output: True (matches "apple" or "apply")
print(ps.searchPrefix("z.."))   # Output: False

Edge Cases

  • Empty string searches.
  • Wildcards at the beginning, middle, or end of the prefix.
  • Multiple consecutive wildcards (e.g., "..e").

Hints

Hint 1

A standard Trie is efficient for exact prefix matching, but how can you modify the search logic to handle the '.' wildcard?

Hint 2

When encountering a '.' during traversal, consider that you must explore all existing child nodes of the current Trie node.

Hint 3

Since the prefix length is relatively short, recursion (Depth-First Search) is a natural approach to explore the branching paths created by wildcards.

Follow-up questions

  • How would you modify your implementation if the wildcard '.' could match zero or more characters (like a glob pattern)?
  • What is the worst-case time complexity of your search function if the prefix contains many wildcards?
  • If memory were a constraint, how could you optimize the Trie node storage to reduce space usage?