Wildcard Predictive Search
At ServiceNow, users frequently search for records and entities within various applications using predictive search. To enhance this experience, we need to implement a robust search capability that can handle simple wildcard patterns. This feature will allow users to quickly find relevant items even when they are unsure of the exact spelling or full name, improving overall productivity and user satisfaction.
Implement the WildcardDictionary class with the following specifications:
WildcardDictionary(words: string[]): Initializes the dictionary with a given list of words. It should efficiently store these words to support subsequent searches.findLongestMatch(pattern: string): string: Given a pattern string, find the longest word from the dictionary that matches this pattern. The pattern can contain lowercase English letters ('a'-'z') and will contain exactly one wildcard character '*'. The wildcard '*' can match any sequence of zero or more lowercase English letters.
"".WildcardDictionary(words: string[])
words: An array of strings, where each string consists of lowercase English letters. These are the words to be stored in the dictionary.findLongestMatch(pattern: string): string
pattern: A string consisting of lowercase English letters and exactly one '*'. The '*' can appear anywhere in the pattern (start, middle, or end).pattern, or an empty string if no match is found.'a'-'z').pattern string will always contain exactly one '*'. You do not need to handle patterns with zero or multiple '*'s.words array might be empty.words and the pattern can be empty strings, although a pattern with * would mean it's at least *.Examples
Example 1
Input:
operations = ["WildcardDictionary","findLongestMatch","findLongestMatch","findLongestMatch"], params = [[["apple","apply","appetizer","banana","band","apricot","axle"]],["app*e"],["ana"],["ap"]]
Output:
[null,"apple","banana","appetizer"]
Note:
["apple","apply","appetizer","banana","band","apricot","axle"].findLongestMatch("app*e"): "apple" is the only word matching this pattern.findLongestMatch("*ana"): "banana" is the only word matching this pattern.findLongestMatch("ap*"): "apple", "apply", "apricot", "appetizer" all match. "appetizer" is the longest.Example 2
Input:
operations = ["WildcardDictionary","findLongestMatch","findLongestMatch"], params = [[["cat","dog","mouse","elephant"]],["dg"],["cx"]]
Output:
[null,"dog",""]
Note:
["cat","dog","mouse","elephant"].findLongestMatch("d*g"): "dog" matches.findLongestMatch("c*x"): No word matches this pattern, so an empty string is returned.Example 3
Input:
operations = ["WildcardDictionary","findLongestMatch"], params = [[["a","aa","aaa","aaaa","aaaaa"]],["a*a"]]
Output:
[null,"aaaaa"]
Note:
["a","aa","aaa","aaaa","aaaaa"].findLongestMatch("a*a"): "aa", "aaa", "aaaa", "aaaaa" all match. "aaaaa" is the longest.Constraints
words.length) will be between 0 and 10^4.words[i].length) will be between 0 and 50.findLongestMatch method will be called up to 10^3 times.pattern string will be between 1 and 50.pattern will contain exactly one '*' character.'a'-'z').'*' wildcard matching zero or more characters.* at the beginning/end, and very short/long words/patterns.Loading editor...