Add and Search Word Design

Design a data structure that supports the following two operations: addWord(word): Adds a word into the data structure. search(pattern): Determines if the pattern exists in the data structure. The pattern can include lowercase letters (a-z), '.' and '', where '.' can match any single letter and '' can match zero or more letters. Example: addWord("coupang") addWord("seoul") addWord("mtv") addWord("mountainview") search("couang.") ➞ false search("coupan.") ➞ true search("c.oupang") ➞ true search("m.v") ➞ true search("m*") ➞ true search("m*ew") ➞ true Example Input addWord car addWord dog search c.r search do.* search .*og search d.g