Frontend School

Wildcard Predictive Search

DSA
hard

Wildcard Predictive Search

Hard
Trie
DFS
String
Wildcard

Overview

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.

What you need to do / Task

Implement the WildcardDictionary class with the following specifications:

  1. Constructor WildcardDictionary(words: string[]): Initializes the dictionary with a given list of words. It should efficiently store these words to support subsequent searches.
  2. Method 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.
    • If multiple words match and have the same maximum length, return any one of them.
    • If no word matches the given pattern, return an empty string "".

Input & output

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).
  • Returns: The longest string from the dictionary that matches the pattern, or an empty string if no match is found.

Clarifications

  • All input words and patterns will only contain lowercase English letters ('a'-'z').
  • The pattern string will always contain exactly one '*'. You do not need to handle patterns with zero or multiple '*'s.
  • The dictionary words array might be empty.
  • Individual words in words and the pattern can be empty strings, although a pattern with * would mean it's at least *.
  • The length of words and patterns can be up to 50 characters.

Examples

1

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:

  1. Initialize with words: ["apple","apply","appetizer","banana","band","apricot","axle"].
  2. findLongestMatch("app*e"): "apple" is the only word matching this pattern.
  3. findLongestMatch("*ana"): "banana" is the only word matching this pattern.
  4. findLongestMatch("ap*"): "apple", "apply", "apricot", "appetizer" all match. "appetizer" is the longest.
2

Example 2

Input:

operations = ["WildcardDictionary","findLongestMatch","findLongestMatch"], params = [[["cat","dog","mouse","elephant"]],["dg"],["cx"]]

Output:

[null,"dog",""]

Note:

  1. Initialize with words: ["cat","dog","mouse","elephant"].
  2. findLongestMatch("d*g"): "dog" matches.
  3. findLongestMatch("c*x"): No word matches this pattern, so an empty string is returned.
3

Example 3

Input:

operations = ["WildcardDictionary","findLongestMatch"], params = [[["a","aa","aaa","aaaa","aaaaa"]],["a*a"]]

Output:

[null,"aaaaa"]

Note:

  1. Initialize with words: ["a","aa","aaa","aaaa","aaaaa"].
  2. findLongestMatch("a*a"): "aa", "aaa", "aaaa", "aaaaa" all match. "aaaaa" is the longest.

Constraints

Constraints & assumptions

  • The number of words in the dictionary (words.length) will be between 0 and 10^4.
  • The length of each word (words[i].length) will be between 0 and 50.
  • The findLongestMatch method will be called up to 10^3 times.
  • The length of the pattern string will be between 1 and 50.
  • Each pattern will contain exactly one '*' character.
  • All characters in words and patterns are lowercase English letters ('a'-'z').

What interviewers evaluate

  • Trie Data Structure Design: Correct and efficient implementation of the Trie for storing words.
  • Wildcard Matching Logic: Ability to correctly implement the recursive search logic to handle the '*' wildcard matching zero or more characters.
  • Algorithmic Efficiency: Optimal time and space complexity for both dictionary construction and search operations, considering the given constraints.
  • Edge Case Handling: Correct behavior for cases like empty dictionary, no matches, patterns with * at the beginning/end, and very short/long words/patterns.
  • Code Clarity and Structure: Readable, well-organized code with appropriate use of helper functions and data structures.

Loading editor...