Design Add and Search Words Data Structure
The key idea
Store words in a trie so shared prefixes collapse into one path. A literal letter follows exactly one child, but a
. wildcard forces a branch: try every child and recurse, succeeding if any branch matches the rest of the query.Problem
Design a data structure that supports adding new words and searching for whether a string matches any previously added word.
Implement the WordDictionary class:
- WordDictionary() creates the object.
- addWord(word) adds word to the data structure so it can later be matched.
- search(word) returns true if there is any added string that equals word, and false otherwise. The search word may contain dots . where a . can match any one letter.
The wildcard makes search powerful: a query of pure letters must match a stored word exactly, but each . is free to stand in for any single character at that position.
Constraints
1 <= word.length <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsists of.or lowercase English letters.- There will be at most
2dots inwordforsearchqueries. - At most
10^4calls will be made toaddWordandsearch.
Examples
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("bad")
Output: true
Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad")
Output: false
Input: addWord("bad"), addWord("dad"), addWord("mad"), search(".ad")
Output: true
Complexity
Time: O(n) per addWord, O(26^d * n) per search with d dots Space: O(N) total characters stored
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization