Problem_5_Search_Suggestions_System.java

package Trie;

// Problem Statement: Search Suggestions System (medium)
// LeetCode Question: 1268. Search Suggestions System

import java.util.ArrayList;
import java.util.List;

public class Problem_5_Search_Suggestions_System {

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }

    class Trie {
        TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        // Inserts a word into the trie
        void insert(String word) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.isEnd = true;
        }

        // Performs a DFS to find all words with the given prefix
        void dfs(TrieNode node, List<String> list, StringBuilder word) {
            if (list.size() == 3) return; // Limit to 3 suggestions
            if (node.isEnd) {
                list.add(word.toString());
            }

            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (node.children[ch - 'a'] != null) {
                    word.append(ch);
                    dfs(node.children[ch - 'a'], list, word);
                    word.deleteCharAt(word.length() - 1);
                }
            }
        }

        // Searches the trie for words starting with prefix
        List<String> search(String prefix) {
            TrieNode node = root;
            List<String> list = new ArrayList<>();

            for (char ch : prefix.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    return list; // No words found with this prefix
                }
                node = node.children[ch - 'a'];
            }

            dfs(node, list, new StringBuilder(prefix));
            return list;
        }
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        for (String product : products) {
            trie.insert(product);
        }

        List<List<String>> result = new ArrayList<>();
        StringBuilder prefix = new StringBuilder();

        for (char ch : searchWord.toCharArray()) {
            prefix.append(ch);
            result.add(trie.search(prefix.toString()));
        }

        return result;
    }

}