Design Add and Search Words Data Structure

Problem

Design a data structure supporting two methods:

• addWord(word) — store word.
• search(word) — return true if any stored word matches word. Here word may contain the wildcard character ., which matches any single letter.

Examples

Constraints

stored words are lowercase a–z, 1–25 characters; search patterns are a–z or ., 1–25 characters; up to 10⁴ calls.

Attempt it first

addWord is just the trie insert you already wrote — nothing changes there. The whole problem lives in search, and specifically in the .. Try it before reading on, and think hard about this: your trie's walk so far has always been deterministic — at each character there was exactly one edge to follow, or none. What does a . do to that? At a ., which child do you descend into?