Frontend School

Shortest Lexicographical Prefix Match

DSA
medium

Shortest Lexicographical Prefix Match

Medium
Trie
String
BFS
Data Structures

Overview

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.

What you need to do / Task

Implement the function findShortestLexicographicalPrefixMatch which takes a list of dictionary words and a query string. Your task is to:

  1. Construct an appropriate data structure (e.g., a Trie) from the dictionary words to enable efficient prefix searching.
  2. For the given query, find all words in the dictionary that start with query.
  3. Among these matching words, identify the one that has the minimum length.
  4. If there are multiple words with the same minimum length, return the one that is lexicographically smallest (i.e., comes first alphabetically).
  5. If no word in the dictionary starts with the query, return an empty string "".

Input & output

  • 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.
  • Returns: A string representing the shortest lexicographical prefix match found, or an empty string "" if no match exists.

Clarifications

  • An empty dictionary will always result in an empty string "".
  • An empty query should match all words in the dictionary. In this case, find the shortest word overall, breaking ties lexicographically.
  • All words in the dictionary are unique.

Examples

1

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).

2

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".

3

Example 3

Input:

dictionary = ["cat", "dog", "cow"], query = "zebra"

Output:

""

Note:

No word in the dictionary starts with "zebra".

4

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).

5

Example 5

Input:

dictionary = ["a", "b", "c"], query = ""

Output:

"a"

Note:

All words have length 1. "a" is lexicographically the smallest.

Constraints

Constraints & assumptions

  • 1 <= dictionary.length <= 10^4
  • 1 <= dictionary[i].length <= 20
  • 0 <= query.length <= 20
  • All characters in dictionary[i] and query are lowercase English letters ('a'-'z').
  • Time complexity for building the dictionary should be efficient (e.g., O(N * L) where N is number of words, L is max word length).
  • Time complexity for each query should be efficient (e.g., O(Q + K) where Q is query length, K is length of matching word found).

What interviewers evaluate

  • Correctness of the Trie implementation and insertion logic.
  • Efficiency of the search algorithm for finding the shortest and lexicographically smallest match.
  • Proper handling of edge cases, including empty inputs and no matches.
  • Code readability, organization, and adherence to best practices.

Loading editor...