Design Add and Search Words Data Structure
Problem
Support two operations: addWord(word) stores a word, and search(pattern) reports whether any stored word matches the pattern. The pattern may contain "." characters, each of which matches any single letter.
Examples
Constraints
- • 1 <= word.length <= 25
- • Search patterns contain at most 2 dots
- • Up to 10^4 calls
Hints & approach
Hint 1
Store the words in a trie as usual.
Hint 2
A normal letter follows exactly one child; a dot must try every child.
Hint 3
Write search as a DFS over (node, index in pattern).
Approachtry the hints first
addWord is plain trie insertion with an end flag. search runs a recursive DFS dfs(node, i). If i equals the pattern length, return node.isEnd. If pattern[i] is a letter, recurse into that child if it exists. If it is ".", recurse into every child and return true as soon as one branch succeeds. With few dots allowed, the branching stays small in practice.
Time O(L) add; O(26^d * L) search with d dots · Space O(total characters)