898. Dotted Word Finder

Medium3.5 points estimatedTrieDesignDepth-First SearchString3 hints
RPby Rohit Parihar

A crossword helper stores a growing word bank and answers pattern queries. Build the class DottedWords with an empty constructor.

  • addWord(word) adds a lowercase word to the bank (adding a duplicate changes nothing).
  • search(word) receives a pattern made of lowercase letters and dots. A dot stands for exactly one arbitrary letter. Return true if some stored word has the same length as the pattern and agrees with it on every non-dot position, otherwise false.

Patterns are never empty, and a pattern consisting only of dots simply asks whether a word of that length exists. Store the words in a tree so that a query does not compare against every word.

Example 1

Input:
operations = ["DottedWords","addWord","addWord","search","search","search","search"]arguments = [[],["tundra"],["tulip"],["tu...a"],["t.l.p"],["tun"],["t.l.q"]]
Output:
[null,null,null,true,true,false,false]
Explanation:

tu...a matches tundra and t.l.p matches tulip; tun is shorter than every stored word.

Example 2

Input:
operations = ["DottedWords","addWord","search","search","search","search"]arguments = [[],["rye"],["..."],["...."],["r.e"],["r.d"]]
Output:
[null,null,true,false,true,false]
Explanation:

A pattern must have exactly the length of the stored word, and each dot stands for one arbitrary letter.

Constraints

1 ≤ word.length ≤ 14

Words passed to addWord contain only lowercase letters; search patterns contain lowercase letters and '.'.

At most 2000 calls in total.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(26^d * L) per search (d = dots), O(L) per addWord
Space
O(total inserted characters)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.