Design Add and Search Words Data Structure
Design a data structure that supports adding words and searching for words.
Implement the WordDictionary class with the following operations:
- addWord(word) — Adds word to the data structure.
- search(word) — Returns true if word matches any previously added word.
The search word may contain the character ..
The character . can represent any single lowercase English letter.
For example:
- search("bad") matches "bad".
- search(".ad") matches "bad", "dad", or "mad".
- search("b..") matches any three-letter word beginning with b.
Example 1
Input
n = 5 addWord bad addWord dad addWord mad search pad search bad
Output
false true
Explanation
The words bad, dad, and mad are inserted.
- pad was not inserted → false
- bad was inserted → true
Example 2
Input
n = 7 addWord bad addWord dad addWord mad search .ad search b.. search ..d search ...
Output
true true true true
Explanation
. represents any single lowercase letter.
Therefore:
- .ad matches bad, dad, or mad.
- b.. matches bad.
- ..d matches all three words.
- ... also matches all three words.
Constraints
Hints:
Hint 1
Use a Trie to store every inserted word.
Hint 2
For normal characters, follow the corresponding child node.
When you encounter ., try all 26 possible child nodes.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 20, 2026
Last updated
Aug 20, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output