Word store with wildcards

mediumTrie (prefix tree)Design as codingRecursion target 25 min

Word store with wildcards

Not solved yetLeetCode 211. Design Add and Search Words Data Structure

Build a class WordDictionary that stores words and checks patterns against them. A pattern is made of lowercase letters and dots, and a dot matches any one letter: the pattern "c.t" matches "cat" and "cot", but not "ct" or "cart".

WordDictionary() makes an empty store.
add_word(word) stores word.
search(pattern) answers True exactly when at least one stored word matches pattern as a whole: the same length, with each letter equal and each dot standing for one letter.

Each WordDictionary() you create starts empty and keeps its own words.

Example 1

Inputadd_word("cat"), add_word("cot"), add_word("dog"), search("c.t"), search("d.t"), search(".o."), search("..")OutputTrue, False, True, False

"c.t" matches "cat". No stored word is d, any letter, t. ".o." matches "cot" and "dog". No stored word has two letters.

Example 2

Inputadd_word("map"), search("ma"), search("ma."), search("map.")OutputFalse, True, False

A pattern must match a whole word: "ma" is too short and "map." is too long.

Constraints

Every stored word has 1 to 25 lowercase English letters.
Every pattern has 1 to 25 characters, each a lowercase letter or a dot, with at most 2 dots.
At most 10⁴ calls in total.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern