1268. Search Suggestions System

 一刷 06/2022

Version #2 Binary Search [TODO]

Version #1 Trie + DFS

Time - build the trie, L is the average length of words, N is the number of words -> O(NL) + search, in our implementation it takes O(1) in each step to find the root trie node of the prefix, then we'll take O(L) time to find each word -> So total is O(NL + 3L) ~ O(NL)

Space - O (26NL)

Runtime: 119 ms, faster than 30.32% of Java online submissions for Search Suggestions System.

Memory Usage: 74.8 MB, less than 36.85% of Java online submissions for Search Suggestions System.

class Solution {

    class TrieNode {

        TrieNode[] children;

        String word;

        public TrieNode() {

            children = new TrieNode[26];

        }

    }

    

    private void addWord(TrieNode root, String word) {

        for (int i = 0; i < word.length(); i++) {

            int index = word.charAt(i) - 'a';

            if (root.children[index] == null) {

                root.children[index] = new TrieNode();

            }

            root = root.children[index];

        }

        root.word = word;

    }

    private void dfs(TrieNode node, int[] size, List<String> list) {

        if (node == null) {

            return;

        }

        if (size[0] == 0) {

            return;

        }

        if (node.word != null) {

            list.add(node.word);

            size[0]--;

        }

        

        for (TrieNode child : node.children) {

            dfs(child, size, list);

        }

    }

    

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {

        TrieNode root = new TrieNode();

        for (String product : products) {

            addWord(root, product);

        }

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

        TrieNode curr = root;

        for (int i = 0; i < searchWord.length(); i++) {

            int index = searchWord.charAt(i) - 'a';

            curr = curr == null ? null : curr.children[index];

            List<String> list = new ArrayList<>();

            dfs(curr, new int[]{3}, list);

            result.add(list);

        }

        return result;

    }

}