Leetcode1268 Search Suggestions System

原文地址

给定一些字符串称为产品和一个搜索词，模拟搜索产品时逐个输入字符时应该输出的结果（产品的前缀等于当前输入）。每次最多给出三个结果并按照字典序排序。

比如products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”]，searchWord = “mouse”

首先输入”m”，按照顺序存在前缀为”m”的产品有[“mobile”,”moneypot”,”monitor”]

…

输入”mou”时，结果只有[“mouse”, “mousepad”]

…依此类推

解法一 前缀二分匹配

实际上就是模拟一个搜索引擎，对搜索词的所有前缀，在产品字符串数组中以前缀二分查找，然后往后最多匹配3个，返回结果。

本题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static int binarySearch(String[] products, String word) {
    int len = word.length();
    int l = 0, r = products.length - 1;
    while (l <= r) {
        int midIdx = l + (r - l) / 2;
        String midWhole = products[midIdx];
        String midSubString = midWhole.substring(0, Math.min(midWhole.length(), len));
        if (midSubString.compareTo(word) < 0) {
            l = midIdx + 1;
        }
        else {
            r = midIdx - 1;
        }
    }
    return l;
}

public static List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    List<List<String>> ans = new ArrayList<>();
    for (int i=1; i<=searchWord.length(); ++i) {
        String word = searchWord.substring(0, i);
        int lowerBound = binarySearch(products, word);
        List<String> res = new ArrayList<>();
        for (int j=lowerBound; j<Math.min(lowerBound+3, products.length); ++j) {
            if (products[j].substring(0, Math.min(products[j].length(), i)).equals(word)) {
                res.add(products[j]);
            }
        }
        ans.add(res);
    }
    return ans;
}

解法二 Trie

来自题解

想到前缀，一个特殊的数据结构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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    //sort words so they will be added in a sorted order to nodes 
    Arrays.sort(products);

    Trie root = new Trie();
    for (String prod : products) {
        Trie n = root;
        for (char ch : prod.toCharArray()) {
            int i = ch - 'a';
            if (n.next[i] == null) {
                n.next[i] = new Trie();
            }
            n = n.next[i];
            if (n.words.size() < 3)
                n.words.add(prod);
        }
    }

    List<List<String>> res = new ArrayList();
    Trie n = root;
    //start going over the search word char by char
    for (int i = 0; i < searchWord.length(); i++) {
        n = n.next[searchWord.charAt(i) - 'a'];
        //if we met null - means no more matches possible, the result of result can be filled by empty lists
        if (n == null) {
            for (int j = i; j < searchWord.length(); j++)
                res.add(Collections.EMPTY_LIST);    
            break;
        }
        res.add(n.words);
    }
    return res;
}
//trie node
class Trie {
    Trie[] next;
    List<String> words;
    Trie() {
        words = new ArrayList();
        next = new Trie[26];
    }
}

最后更新： 2020年06月09日 21:57

原始链接： http://roooooobin.github.io/2020/06/08/Search-Suggestions-System-Solution/

赏
× thanks~
打赏二维码