🧺 Space complexity: O(n)

Method 2 - Using Trie

Using a Trie data structure can significantly optimise prefix matching in this problem. Here's the reasoning, approach, and implementation for solving it with a Trie.

Reasoning

A Trie is a tree-based data structure used for efficiently storing strings. Each node represents a character. Using a Trie, we can:

Quickly insert products into the structure with their prefixes.
Efficiently find all product names matching a prefix by traversing nodes.

We will preprocess the products list into a Trie, then for each prefix formed by searchWord, perform a traversal to obtain at most three lexicographically smallest suggestions.

Approach

Build the Trie:
- Construct the Trie using products.
- Each node contains a list of references to at most three lexicographically smallest products at that prefix.
Query the Trie for Prefix Suggestions:
- For each prefix created by typing characters in searchWord, traverse the Trie to find suggested products.
Suggestion Limitation:
- While constructing the Trie and storing products at each node, maintain only the first three lexicographically smallest product names.

Code

[{"language":"Java","code":"class Solution {\n    class TrieNode {\n        Map<Character, TrieNode> children = new HashMap<>();\n        List<String> suggestions = new ArrayList<>();\n    }\n    \n    private void insertProduct(TrieNode root, String product) {\n        TrieNode current = root;\n        for (char ch : product.toCharArray()) {\n            current.children.putIfAbsent(ch, new TrieNode());\n            current = current.children.get(ch);\n            \n            // Maintain at most 3 lexicographical suggestions at each node\n            if (current.suggestions.size() < 3) {\n                current.suggestions.add(product);\n            }\n        }\n    }\n    \n    private List<String> searchSuggestions(TrieNode root, String prefix) {\n        TrieNode current = root;\n        for (char ch : prefix.toCharArray()) {\n            current = current.children.get(ch);\n            if (current == null) {\n                return new ArrayList<>();\n            }\n        }\n        return current.suggestions;\n    }\n    \n    public List<List<String>> suggestedProducts(String[] products, String searchWord) {\n        TrieNode root = new TrieNode();\n        Arrays.sort(products); // Sort products lexicographically\n        \n        // Constru

Related Tags