Frontend School

Longest Matching Dictionary Prefixes

DSA
medium

Longest Matching Dictionary Prefixes

Medium
Trie
String
Prefix Search

Overview

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.

What you need to do / Task

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.

  1. Construct a suitable data structure from the dictionary words to enable efficient prefix searching.
  2. For each searchTerm in the searchTerms list:
    • Find the longest word from the dictionary that is a prefix of the current searchTerm.
    • If multiple words from the 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.
    • If no word from the dictionary is a prefix of the searchTerm, the result for that searchTerm should be an empty string "".
  3. Return a list of these longest matching prefixes, maintaining the original order of searchTerms.

Input & output

  • dictionary: string[]
    • An array of strings representing the available terms in the dictionary.
    • Each string consists of lowercase English letters.
  • searchTerms: string[]
    • An array of strings representing the user's search queries.
    • Each string consists of lowercase English letters.
  • Returns: string[]
    • An array of strings, where each element i is the longest matching dictionary prefix for searchTerms[i]. If no prefix is found, it should be an empty string "".

Clarifications

  • Case Sensitivity: Assume all input words and search terms are in lowercase English letters. No need to handle mixed case.
  • Empty Inputs: If dictionary is empty, all results in the output array should be empty strings. If searchTerms is empty, the function should return an empty array.
  • Exact Match: If a 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".
  • Longest Prefix Definition: A word 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

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= dictionary.length <= 10^4
  • 1 <= searchTerms.length <= 10^4
  • 1 <= dictionary[i].length, searchTerms[i].length <= 50
  • All characters in dictionary[i] and searchTerms[i] are lowercase English letters ('a'-'z').
  • The total number of characters across all dictionary words and search terms is within reasonable limits for typical string operations (e.g., sum(len(word)) for dictionary and sum(len(term)) for search terms are less than 5 * 10^5).

Out of scope

  • Handling non-alphabetic characters, numbers, or special symbols.
  • Optimizing for memory usage beyond a standard Trie implementation.

What interviewers evaluate

  • Correctness and Efficiency: The solution must correctly identify the longest prefixes and operate efficiently within the given constraints.
  • Trie Implementation: Demonstrating a solid understanding and correct implementation of a Trie data structure.
  • Edge Case Handling: Ability to handle various edge cases, such as empty inputs, no matching prefixes, or exact matches.
  • Code Quality: Clear, well-structured, and readable code, with appropriate comments where necessary.

Loading editor...