Design Add and Search Words Data Structure

MediumTreestrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Build a dictionary of words that supports wildcard lookups. In a query, the character . matches **exactly one** arbitrary letter; every other character must match literally. A query only matches words of the same length. Implement: - WordDictionary() creates an empty dictionary. - addWord(word) stores word (lowercase letters only). - search(word) returns true if some stored word matches the pattern word, otherwise false. Queries contain lowercase letters and at most 2 dots.

Examples

Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search","search"] [[],["cat"],["cot"],["dog"],["c.t"],["..g"],["c..t"],["cut"],["..."]]
Output: [null,null,null,null,true,true,false,false,true]
"c.t" matches "cat", "..g" matches "dog", "c..t" has the wrong length, "cut" was never added, and "..." matches any stored three-letter word.
Input: ["WordDictionary","search","addWord","search"] [[],["a"],["a"],["."]]
Output: [null,false,null,true]
Nothing matches in an empty dictionary. After adding "a", the one-character wildcard matches it.

Constraints

  • 1 <= word.length <= 25
  • `addWord` receives lowercase letters only.
  • `search` receives lowercase letters and at most 2 `.` characters.
  • At most 10^4 calls in total.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems