DSA · Trie / Design · #64

Design Add and Search Words Data Structure

Module 56 · difficulty 3/5·⏱ 30:00starts on first keystroke

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the `WordDictionary` class: - `WordDictionary()` initializes the object. - `void addWord(word)` adds `word` to the data structure so it can be matched later. - `boolean search(word)` returns `true` if there is any string in the data structure that matches `word`, otherwise `false`. `word` may contain the dot character `.`, where a `.` can match **any single letter**. The entry class name is `WordDictionary`.

Examples

addWord("bad"); addWord("dad"); addWord("mad"); search("pad"); search("bad"); search(".ad"); search("b.."); → [null, null, null, false, true, true, true] — `.ad` matches bad/dad/mad; `b..` matches bad.
addWord("a"); search("."); search("a"); search("aa"); → [null, true, true, false] — `.` matches the single-letter word a; `aa` has no match.

Constraints

· 1 <= word.length <= 25
· word in addWord consists of lowercase English letters.
· word in search consists of '.' or lowercase English letters.
· There are at most 2 dots in word for search queries when calling search.
· At most 10^4 calls will be made to addWord and search.

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.