Design Add And Search Words Data Structure
Implement WordDictionary with addWord(word) and search(pattern). In a search pattern, a dot matches exactly one lowercase letter. Return whether any added word matches the complete pattern.
Example 1
arg 1 = ["WordDictionary","addWord","addWord","search","search","search","search"]
arg 2 = [[],["cat"],["cap"],["ca."],["c.."],[".."],["dog"]][null,null,null,true,true,false,false]Explanation
ca. and c.. match cat or cap; .. has the wrong length and dog matches neither.
Example 2
arg 1 = ["WordDictionary","addWord","search","search"]
arg 2 = [[],["a"],["."],[".."]][null,null,true,false]Explanation
One dot matches a; two dots require two letters and fail.
Example 3
arg 1 = ["WordDictionary","addWord","search","addWord","search","search"]
arg 2 = [[],["cat"],["d.g"],["dog"],["d.g"],["dog"]][null,null,false,null,true,true]Explanation
d.g cannot match cat, but after adding dog both d.g and dog match.
Constraints
- At most 10000 operations
- Words and patterns have 1..25 characters
- Stored words contain lowercase English letters
- Patterns additionally allow dots
Class contract
WordDictionaryArguments: json, jsonSolutionRuns on your device
Loading draft…
Run: 3 examples; Submit: 35 cases, on your device.
["WordDictionary","addWord","addWord","search","search","search","search"][[],["cat"],["cap"],["ca."],["c.."],[".."],["dog"]]