90. Word Dictionary with Wildcard Search
Store lowercase words and answer search patterns in which a dot matches exactly one letter. A match must cover an entire stored word, not merely a substring or prefix.
This is not a general regular-expression language. Validate unsupported characters and keep search operations from changing the stored dictionary.
Example 1
Input
add bad,dad,mad; search .ad
Output
true
Explanation: A dot explores existing first-letter alternatives; the remaining literal suffix must match.
Example 2
Input
add bad; search ba
Output
false
Explanation: The ba path exists but is not a complete stored word.
Example 3
Input
add empty word; search empty pattern
Output
true
Explanation: Zero characters consume zero edges, so only root terminal state decides.
Constraints
0 <= word.length, pattern.length <= 1040 <= total added characters <= 105- Stored words contain lowercase English letters. A search dot matches exactly one letter.
Hints
Hint 1
A trie path is not necessarily a stored complete word.
Hint 2
A dot branches over children and consumes exactly one position.
Hint 3
Store (node,index) states; accept only an exhausted terminal state.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Whole words, prefix-only paths, and wildcard branching
[["add","bad"],["add","dad"],["add","mad"],["search","pad"],["search",".ad"],["search","ba"],["add","ba"],["search","ba"]]
[null,null,null,false,true,false,null,true]