Trie + HashMap Based String Pattern Matching

Problem Statement

Design a data structure that supports the following operations on a collection of strings:

1. insert(word) — Adds a word to the collection
2. search(pattern) — Returns all words that match a given pattern, where the pattern may contain wildcard characters

The wildcard . matches any single character. You need to optimize the search to be significantly faster than brute-force checking every word.

Constraints

• 1 <= word.length <= 25
• 1 <= pattern.length <= 25
• Words consist of lowercase English letters
• Pattern consists of lowercase English letters and .
• At most 10^4 calls to insert and search combined

Example

insert("apple")
insert("apply")
insert("ape")
insert("bat")

search("ap.le")  → ["apple"]
search("app..")  → ["apple", "apply"]
search("a.e")    → ["ape"]
search("b.t")    → ["bat"]

Follow-ups

1. What if the wildcard * matches zero or more characters? How does your approach change?
2. How would you handle prefix-based search efficiently alongside wildcard search?
3. What's the time complexity of search in the worst case? Can you bound it?
4. How would you modify this for case-insensitive matching?