Shortest Lexicographical Prefix Match
A common challenge in large-scale data processing or search systems is efficiently retrieving information based on prefixes while adhering to specific criteria. For instance, an autocomplete system might need to suggest the shortest, most relevant word that matches a user's partial input. This problem explores how to leverage a Trie data structure to solve such a task efficiently, focusing on optimized search and tie-breaking rules.
Implement the function findShortestLexicographicalPrefixMatch which takes a list of dictionary words and a query string. Your task is to:
dictionary words to enable efficient prefix searching.query, find all words in the dictionary that start with query.dictionary starts with the query, return an empty string "".dictionary: An array of strings, where each string is a word to be added to the internal data structure. All words consist of lowercase English letters.query: A string representing the prefix to search for. It consists of lowercase English letters."" if no match exists.dictionary will always result in an empty string "".query should match all words in the dictionary. In this case, find the shortest word overall, breaking ties lexicographically.dictionary are unique.Examples
Example 1
Input:
dictionary = ["apple", "apply", "app", "apricot", "banana"], query = "ap"
Output:
"app"
Note:
Words starting with "ap" are "apple", "apply", "app", "apricot". Their lengths are 5, 5, 3, 7 respectively. The shortest word is "app" (length 3).
Example 2
Input:
dictionary = ["apple", "apply", "apricot", "banana"], query = "appl"
Output:
"apple"
Note:
Words starting with "appl" are "apple", "apply". Both have length 5. Lexicographically, "apple" comes before "apply".
Example 3
Input:
dictionary = ["cat", "dog", "cow"], query = "zebra"
Output:
""
Note:
No word in the dictionary starts with "zebra".
Example 4
Input:
dictionary = ["zebra", "apple", "cat"], query = ""
Output:
"cat"
Note:
An empty query matches all words. "cat" (length 3) is the shortest among "zebra" (5), "apple" (5), "cat" (3).
Example 5
Input:
dictionary = ["a", "b", "c"], query = ""
Output:
"a"
Note:
All words have length 1. "a" is lexicographically the smallest.
Constraints
1 <= dictionary.length <= 10^41 <= dictionary[i].length <= 200 <= query.length <= 20dictionary[i] and query are lowercase English letters ('a'-'z').Loading editor...