Search Suggestions System

1package pkg5leetcode.official75;2 3/*4 * Search Suggestions System | LC 12685 * APPROACH: Trie DFS collect up to 3 words per prefix.6 * COMPLEXITY: Time O(n * avg_len), Space O(total chars)7 */8import java.util.*;9 10public class official75_LC1268SearchSuggestionsSystem {11    static class TrieNode {12        TrieNode[] child = new TrieNode[26];13        List<String> words = new ArrayList<>();14    }15 16    static List<List<String>> suggestedProducts(String[] products, String searchWord) {17        Arrays.sort(products);18        TrieNode root = new TrieNode();19        for (String p : products) {20            TrieNode node = root;21            for (char c : p.toCharArray()) {22                int i = c - 'a';23                if (node.child[i] == null) node.child[i] = new TrieNode();24                node = node.child[i];25                if (node.words.size() < 3) node.words.add(p);26            }27        }28        List<List<String>> res = new ArrayList<>();29        TrieNode node = root;30        for (char c : searchWord.toCharArray()) {31            if (node == null) { res.add(Collections.emptyList()); continue; }32            node = node.child[c - 'a'];33            res.add(node == null ? Collections.emptyList() : node.words);34        }35        return res;36    }37 38    public static void main(String[] args) {39        List<List<String>> r = suggestedProducts(40                new String[]{"mobile","mouse","moneypot","monitor","mousepad"}, "mouse");41        check(r.get(0).equals(Arrays.asList("mobile","moneypot","monitor")), "case1");42        check(r.get(3).equals(Arrays.asList("mouse","mousepad")), "case4");43        System.out.println("all tests passed");44    }45 46    static void check(boolean cond, String name) {47        if (!cond) throw new AssertionError("FAILED: " + name);48        System.out.println("  PASS " + name);49    }50}