Design Add and Search Words Data Structure — Medium Coding Interview Question

Design a data structure supporting addWord(word) and search(word) where word may contain '.' matching any letter.

Example

Input: addWord("bad"), search(".ad") -> true

Output: true

Topics: trie, backtracking

Asked by: Meta, Amazon

Time complexity: O(N * 26^M). Space complexity: O(N).