Design Add and Search Words

LRU Cache

Implement Trie

Build a trie that supports exact letters and wildcard searches.

Execute `add` and `search` operations. In searches, `.` matches any single letter. Return search results as `1` for true and `0` for false, in order.

## Example
```json
Input: {"operations":["add","add","add","search","search","search","search"],"words":["bad","dad","mad","pad","bad",".ad","b.."]}
Output: [0,1,1,1]
```

## Constraints
- 1 <= operations.length == words.length <= 10000
- Search words contain lowercase letters or `.`

## Follow-up
Why can wildcard-heavy searches become exponential in word length?

The key pattern is: Trie search backtracks across children for wildcard positions. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(total add characters + wildcard search branches). Space: O(total inserted characters).