Katkat
Back

First Word Matching Each Prefix Query

PinterestMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently query a list of strings to find the first occurrence that matches a given prefix, focusing on optimal space-time tradeoffs using tree-based or map-based indexing.

Problem Statement

Given a list of words dictionary and a list of query strings prefixes, return an array of strings where the i-th element is the first string in dictionary that starts with prefixes[i]. If no word in the dictionary matches the prefix, return an empty string.

Function Signature

def find_first_matches(dictionary: List[str], prefixes: List[str]) -> List[str]:

Constraints

  • dictionary contains up to 10^5 strings, each with length up to 50.
  • prefixes contains up to 10^5 queries, each with length up to 50.
  • Total characters across all strings in the dictionary will not exceed 2 * 10^6.

Example 1

Input: dictionary = ["apple", "appetizer", "apply", "banana"] prefixes = ["app", "ban", "ape"]

Output: ["apple", "banana", ""]

Explanation:

  • "app" matches "apple" (first index 0).
  • "ban" matches "banana" (first index 3).
  • "ape" has no match in the dictionary.

Example 2

Input: dictionary = ["cat", "car", "camera"] prefixes = ["ca"]

Output: ["cat"]

Edge Cases

  • Empty dictionary or empty prefixes list.
  • Prefixes longer than any word in the dictionary.
  • Duplicate prefixes in the query list.

Hints

Hint 1

Consider pre-processing the dictionary into a data structure that allows for fast prefix-based lookups.

Hint 2

A Trie can store the dictionary, but how can you store the 'first' index or string efficiently within each node?

Hint 3

Alternatively, could you use a hash map to store every possible prefix of each word, keeping only the first word encountered for each unique prefix?

Follow-up questions

  • How would your approach change if the dictionary was updated dynamically (e.g., words added or removed)?
  • What is the space complexity of your solution, and how would you optimize memory if the dictionary contained millions of very long strings?
  • If the query list is significantly smaller than the dictionary size, would a different approach be more efficient?