DSA problem
Design Add and Search Words Data Structure
Design a data structure that supports adding words from a dictionary and later searching for words, where the search query may contain regular letters or the wildcard . matching any single character. Implement the WordDictionary class with two operations: addWord(word) adds the word to the dictionary, and search(word) returns true if any previously added word matches the query.
A naive solution stores all words in a list or hash set and scans them for every query, but in the worst case the search cost is O(N * L) per query for N stored words of length L — far too slow for the constraint of up to 10^4 calls. Worse, the presence of wildcards rules out direct hashing.
The clean approach is to insert every word into a trie, which lets ordinary letter searches succeed in O(L) by walking a single path. The interesting twist is the dot wildcard: when the search character is ., the algorithm must consider every existing child of the current node, not just one specific letter.
A depth-first search handles this elegantly. The recursion takes the current node and the current index into the query string. For a normal character it descends into exactly one child; for . it iterates over all 26 children and recurses into each non-null one, returning true if any branch finds a match. The terminal check, exactly as in a plain trie, is whether the final node has isEnd = true. Average case stays near O(L); the worst case degenerates to O(26^d * L) where d is the number of dots, which is acceptable because queries are short.
Examples
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]][null,null,null,null,false,true,true,true]["WordDictionary","addWord","search"]
[[],["a"],["."]][null,null,true]["WordDictionary","addWord","addWord","search"]
[[],["at"],["and"],["..."]][null,null,null,true]Constraints
- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters.
- word in search consists of '.' or lowercase English letters.
- There will be at most 2 dots in word for search queries.
- At most 10^4 calls in total will be made to addWord and search.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.