MEDIUM NC#62 Blind #72 Trie / Data Structure Design
211. Design Add and Search Words Data Structure
📖 Problem
Design a data structure that supports adding new words and finding if a string matches any previously added word. Implement the WordDictionary class: - WordDictionary() Initializes the object. - addWord(word) Adds word to the data structure, word can consist of lowercase English letters. - search(word) Returns true if there is any word in the data structure that matches word. word may contain dots '.' where dots can match any single letter.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
💡 Approach
- → Use Trie for efficient prefix search
- → For wildcards, check all possible matches
- → Insert time: O(m), Search time: O(m * 26^k) worst case
- → Space: O(n * m) for storing words
🛠️ Hints & Pitfalls
Hints
- •Use Trie for efficient prefix search
- •For wildcards, check all possible matches
- •Insert time: O(m), Search time: O(m * 26^k) worst case
Common Pitfalls
- •Space: O(n * m) for storing words
🧪 Test Cases
Hidden tests on submit: 4
Test Case 1
Not run Input:
(() => { const wordDict = new WordDictionary(); return wordDict.addWord('bad'); })(); Expected:
null Test Case 2
Not run Input:
(() => { const wordDict = new WordDictionary(); wordDict.addWord('bad'); return wordDict.addWord('dad'); })(); Expected:
null Test Case 3
Not run Input:
(() => { const wordDict = new WordDictionary(); wordDict.addWord('bad'); wordDict.addWord('dad'); return wordDict.addWord('mad'); })(); Expected:
null 📝 Code Editor
📤 Output