Word Dictionary with Wildcards
Learn this problem
DatadogINTERNPHONE SCREENProblem statement
Implement the behavior of a word dictionary that supports two operations:
["add", word]adds the literal lowercase word.["search", pattern]asks whether any added word matches the complete pattern.
Within a search pattern, a period . is a wildcard that matches exactly one lowercase English letter. All other characters match themselves. The wildcard never matches zero characters or more than one character.
Process the rows of operations in order and return a boolean result for every search row, in the same order. Repeated additions are allowed.
Function
wordDictionary(operations: String[][]) → boolean[]Examples
Example 1
operations = [["add","bad"],["add","dad"],["add","mad"],["search","pad"],["search","bad"],["search",".ad"],["search","b.."]]return = [false,true,true,true]pad was never added. The literal bad, wildcard .ad, and wildcard b.. each match an added word.
Example 2
operations = [["add","a"],["add","at"],["search","."],["search","a."],["search","..."]]return = [true,true,false]A wildcard matches exactly one character, so the first two searches match lengths one and two, while no three-letter word exists.
Example 3
operations = [["search","."],["add","z"],["search","."]]return = [false,true]Operations are processed sequentially, so the same pattern fails before z is added and succeeds afterward.
Constraints
1 <= operations.length <= 100000- Every row has exactly two strings.
- The first string is
addorsearch. - Added words contain lowercase English letters only.
- Search patterns contain lowercase English letters and periods only.
1 <= word.length, pattern.length <= 25- At least one operation is a search.