Longest Matching Dictionary Prefixes
In financial trading platforms like Zerodha, users often search for specific instruments or terms. An efficient auto-suggestion or search feature needs to quickly identify the most relevant (longest) matching term from a predefined dictionary as the user types. This problem simulates such a scenario, focusing on finding the longest dictionary word that serves as a prefix for various user search queries.
Your task is to implement a function that processes a given dictionary of words and a list of search terms. For each search term, you must identify the longest word from the dictionary that is a prefix of that search term.
dictionary words to enable efficient prefix searching.searchTerm in the searchTerms list:
dictionary that is a prefix of the current searchTerm.dictionary are the longest valid prefix (e.g., if the dictionary contains both "abc" and "abcd" and the search term is "abcde", "abcd" is the longest), any one of them is acceptable. However, in this problem's context, there will typically be a unique longest one.dictionary is a prefix of the searchTerm, the result for that searchTerm should be an empty string "".searchTerms.dictionary: string[]
searchTerms: string[]
string[]
i is the longest matching dictionary prefix for searchTerms[i]. If no prefix is found, it should be an empty string "".dictionary is empty, all results in the output array should be empty strings. If searchTerms is empty, the function should return an empty array.searchTerm itself is present in the dictionary, it should be considered the longest prefix if no longer dictionary word is also a prefix of it. For example, if dictionary = ["apple"] and searchTerm = "apple", the result is "apple".P is a prefix of word S if S starts with P. We are looking for the longest such P that also exists in the dictionary.Examples
Example 1
Input:
dictionary = ["apple", "apricot", "banana", "band"], searchTerms = ["appletree", "bandana", "orange", "apple"]
Output:
["apple", "band", "", "apple"]
Note:
For "appletree", "apple" is the longest dictionary prefix. For "bandana", "band" is the longest. "orange" has no dictionary prefix. "apple" itself is found in the dictionary.
Example 2
Input:
dictionary = ["a", "b", "c", "applepie"], searchTerms = ["apricot", "banana", "apple", "applepie"]
Output:
["a", "b", "a", "applepie"]
Note:
For "apricot" and "apple", "a" is the longest prefix. For "banana", "b" is. For "applepie", the exact match is found.
Example 3
Input:
dictionary = ["stock", "stockbrocker", "st"], searchTerms = ["stockbrockerage", "stockholm", "test"]
Output:
["stockbrocker", "stock", ""]
Note:
For "stockbrockerage": "st", "stock", "stockbrocker" are prefixes. The longest is "stockbrocker". For "stockholm": "st", "stock" are prefixes. "stockbrocker" is not. The longest is "stock". For "test": No dictionary word is a prefix, so an empty string is returned.
Constraints
1 <= dictionary.length <= 10^41 <= searchTerms.length <= 10^41 <= dictionary[i].length, searchTerms[i].length <= 50dictionary[i] and searchTerms[i] are lowercase English letters ('a'-'z').sum(len(word)) for dictionary and sum(len(term)) for search terms are less than 5 * 10^5).Loading editor...