1268. Search Suggestions System

Posted on | Edited on | Views:

LeetCode

link
Approach 1: Trie, Time: O(key_length), Space: O(ALPHABET_SIZE · key_length · N) where N is number of keys in Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Trie{
    Trie[] sub=new Trie[26];
    LinkedList<String> suggestion=new LinkedList<>();
}
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie root=new Trie();
        Arrays.sort(products);
        for(String product:products){
            Trie p=root;
            for(char ch:product.toCharArray()){
                if(p.sub[ch-'a']==null) p.sub[ch-'a']=new Trie();
                p=p.sub[ch-'a'];
                if(p.suggestion.size()<3) p.suggestion.offer(product);
            }
        }
        List<List<String>> ans=new ArrayList<>();
        for(char ch:searchWord.toCharArray()){
            if(root!=null) root=root.sub[ch-'a'];
            ans.add(root==null?new ArrayList():root.suggestion);
        }
        return ans;
    }
}

link
Approach 2: Sort and Binary Search the Prefix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        TreeMap<String, Integer> map = new TreeMap<>();
        Arrays.sort(products);
        List<String> productsList = Arrays.asList(products);

        for (int i = 0; i < products.length; i++) {
            map.put(products[i], i);
        }

        String key = "";
        for (char c : searchWord.toCharArray()) {
            key += c;
            String ceiling = map.ceilingKey(key);
            String floor = map.floorKey(key + "~");
            if (ceiling == null || floor == null) break;
            res.add(productsList.subList(map.get(ceiling), Math.min(map.get(ceiling) + 3, map.get(floor) + 1)));
        }

        while (res.size() < searchWord.length()) res.add(new ArrayList<>());
        return res;
    }*/

0%