Trie-based Prefix Counter
Paytm operates at immense scale, processing millions of transactions and managing vast directories of merchants and products. Efficiently searching and retrieving data based on partial inputs is a critical capability. This problem simulates a core component of such systems: designing a data structure to quickly determine the number of items that match a given prefix.
Implement a function getPrefixCounts that takes two arrays of strings: dictionary and queries. Your task is to build an efficient data structure from the dictionary and then, for each string in queries, find and return the total count of words in the dictionary that start with that particular query string as a prefix.
dictionary: An array of strings representing the collection of words to be indexed. Each string in this array is considered a distinct item, even if duplicate strings exist.queries: An array of strings representing the prefixes for which you need to find counts.i-th element of the returned array should be the count of words in the dictionary that have queries[i] as their prefix.dictionary and queries will consist only of lowercase English letters ('a'-'z')."") should return the total count of words in the dictionary if encountered in queries.Examples
Example 1
Input:
dictionary = ["apple", "apricot", "application", "banana"], queries = ["app", "apr", "ban", "gra"]
Output:
[2,1,1,0]
Note:
For "app", "apple" and "application" are matches (count = 2). For "apr", "apricot" is a match (count = 1). For "ban", "banana" is a match (count = 1). For "gra", no words match (count = 0).
Example 2
Input:
dictionary = ["cat", "car", "dog", "catamaran"], queries = ["ca", "c", "do", "d"]
Output:
[3,3,1,1]
Note:
For "ca", "cat", "car", "catamaran" are matches (count = 3). For "c", "cat", "car", "catamaran" are matches (count = 3). For "do", "dog" is a match (count = 1). For "d", "dog" is a match (count = 1).
Example 3
Input:
dictionary = ["test", "tester", "test"], queries = ["test", "tes", "t"]
Output:
[2,3,3]
Note:
For "test", both instances of "test" are matches (count = 2). For "tes", both instances of "test" and "tester" are matches (count = 3). For "t", both instances of "test" and "tester" are matches (count = 3).
Constraints
1 <= dictionary.length <= 10^41 <= queries.length <= 10^41 <= dictionary[i].length, queries[i].length <= 30dictionary and queries consist of lowercase English letters ('a'-'z').dictionary should be handled such that each occurrence contributes to the prefix count (e.g., if dictionary = ["apple", "apple"] and query = "app", the count should be 2).Loading editor...