Design Add and Search Words Data Structure
Part of Practice: Build & Search Tries
Design a data structure that stores words and supports searching with a wildcard. It has two operations:
addWord(word): store a word made of lowercase letters.search(word): return true if any stored word matches. The query may contain.characters, and each.matches exactly one letter — any letter.
Words are up to 25 characters, queries contain at most 2 dots, and there can be up to 10,000 calls total. A match must use the whole word: same length, every position compatible.
Examples
- Input:
- addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
- Output:
- null, null, null, false, true, true, true
"pad" matches nothing stored. "bad" is an exact match. ".ad" matches "bad", "dad", and "mad" since the dot can be any letter. "b.." matches "bad".
- Input:
- addWord("a"), search("."), search("a."), search(".a")
- Output:
- null, true, false, false
"." matches the one-letter word "a". Both two-character queries fail because no stored word has length 2 — a dot matches exactly one letter, never zero.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.