Word Dictionary with Wildcard Find
Amazon● MediumFULLTIMEONSITE INTERVIEWProblem statement
Build a word dictionary that supports inserting words and finding words with wildcards. Process the rows of operations from left to right. The dictionary starts empty, and each row has one of these forms:
["insert", word]addswordto the dictionary. Inserting a word that is already present changes nothing.["find", pattern]asks whether the dictionary currently holds at least one word that matchespattern.
A pattern matches a word when both have the same length and, at every position, the pattern character is either the same letter or a period .. A period is a wildcard that matches exactly one lowercase letter. It never matches zero letters or more than one letter.
Examples
Example 1
operations = [["insert","cat"],["insert","car"],["insert","cart"],["find","ca."],["find","c..t"],["find","ca"],["find","d.."]]return = [true,true,false,false]The pattern ca. matches both cat and car, so the first answer is true. The pattern c..t has length 4 and matches cart. No stored word has length 2, so ca is false. Every stored word starts with c, so d.. is false.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.