LeetCode 211 Design Add and Search Words - Example and Complexity Analysis

Trie contains "bad", "dad", "mad". Search ".ad".

At root, pattern is ".ad". The . matches any child. Root has children: b, d, m.

Branch 1: follow 'b'. Pattern remaining: "ad". Match 'a' → 'd'. Reach end, is word? Yes. Return true.

If we had continued: branch 2 (d → a → d) also matches, branch 3 (m → a → d) also matches.

For "b..": follow 'b', then . matches 'a', then . matches 'd'. Found "bad".

Add: $O(m)$ where $m$ is word length. Search without wildcards: $O(m)$. Search with wildcards: worst case $O(26^w \cdot m)$ where $w$ is number of wildcards, but typically much faster due to pruning.

Space: $O(T)$ for total characters stored.