Trie
LC #211Medium
Design Add and Search Words Data Structure
Trie
AmazonGoogleMetaProblem
Design a data structure that supports adding words and searching with '.' as wildcard.
triedesigndfs
Constraints
- ›1 ≤ word.length ≤ 25
- ›word in addWord consists of lowercase English letters
- ›word in search consist of '.' or lowercase English letters
- ›At most 10⁴ calls total
Example
Input
addWord("bad"), addWord("dad"), search("pad"), search("bad"), search(".ad"), search("b..")Output
false, true, true, trueWhy
'.' matches any letter. ".ad" matches "bad" or "dad". "b.." matches "bad"