Wildcard Word Registry
MediumTries & Strings
Problem
A crossword helper stores words and answers pattern lookups. You receive operations ops, each [command, value]:
["add", w] stores the word w. ["find", p] asks whether some stored word matches the pattern p, where a . matches exactly one arbitrary letter and every other character must match itself. The word and the pattern must have the same length.
Return the answers to the find operations, in order.
Example 1
- Input:
- ops = [["add","lamp"],["add","limp"],["add","lump"],["find","l.mp"],["find","lam"],["find","...."],["find","l..k"],["find","lamps"]]
- Output:
- [true, false, true, false, false]
"l.mp" matches all three words; "lam" is only a prefix; no stored word ends in k.
Example 2
- Input:
- ops = [["find","a"],["add","a"],["find","."],["find",".."]]
- Output:
- [false, true, false]
Constraints
- 1 ≤ ops.length ≤ 10^4
- 1 ≤ value.length ≤ 25
- Words are lowercase letters; patterns are lowercase letters or '.'.
- A pattern contains at most 3 dots.
Hint
Show the first hint
Without dots this is an exact trie lookup. What changes when a dot appears?
Walkthrough
How to approach it
01Clarify before coding
- Does a dot match an empty position? No, exactly one letter, so lengths must be equal.
- Can a stored word itself contain a dot? No, only patterns do.
- How many dots? At most 3, which bounds the branching.
02Brute force
Keep words in a list; for each find, compare the pattern against every word of the same length.
Cost: O(N·L) per query: 10^4 words · 25 letters for each of 10^4 queries, about 2.5·10^9 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.