Step through efficient trie implementations to optimize search suggestions, word replacements, and common prefix finding.

Coding

Organizes data in a tree structure where each node represents a character, enabling efficient insertion, deletion, and search operations for words.

Trie

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral


# Statement

Given an array of strings called `products` and a word to search, design a system that, when each character of the searched word is typed, suggests at most three product names from `products`. Suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, return the three product names that appear first in lexicographical order.

Return the suggested products, which will be a list of lists after each character of searched word is typed.

**Constraints:**
* $1 \leq$ `products.length` $\leq 1000$
* $1 \leq$ `products[i].length` $\leq 3000$
* $1 \leq$ `sum(products[i].length)` $\leq 2 \times 10^3$
* All the strings of products are unique.
* `products[i]` consists of lowercase English letters.
* $1 \leq$ `searched word.length` $\leq 1000$
* The searched word consists of lowercase English letters.

# Solution

So far, you've probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.



## Naive approach

A naive approach would be to first sort the given product data in lexicographic order to help with retrieving three matching products. Next, we iterate each character of the searched word, adding the current character to the substring to search for. We'll search in the list of product names to check whether the current substring exists or not. If it exists, we'll store the results (containing matching product names) for the current substring. We'll repeat this process until we have traversed the whole list of product names.

It takes $O(n\log n)$ time to sort the given data, where $n$ is the number of product names. Given that $m$ is the number of characters in the search word, there will be $m$ substrings derived from the search word. So, it will take $O(m\times n)$ time to find the matching product names for all the substrings derived from the search word. So, the total time complexity of the search is $O(m\times n + n \log n)$. The space complexity of this solution is $O(m)$, since we're using a variable to store the current prefix to search for.


## Optimized approach using trie

The idea is to reduce the time complexity using the trie pattern. Although it will increase the space complexity a bit, it will help us reduce the time complexity to a great extent. We can feed the products' data into the system and create a trie out of it. Next, we can search for the required product in the recorded data.



Let's solve the Search Suggestions System problem using the Trie pattern.

Solution: Search Suggestions System

Statement▼

Solution: Search Suggestions System

Statement▼