rustgym/leetcode/
_1268_search_suggestions_system.rs

1struct Solution;
2use std::usize;
3
4impl Solution {
5    fn suggested_products(mut products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
6        let mut res = vec![];
7        products.sort_unstable();
8        let n = products.len();
9        let mut prefix = "".to_string();
10        let mut start = 0;
11        for c in search_word.chars() {
12            prefix.push(c);
13            start = start
14                + products[start..]
15                    .binary_search(&prefix)
16                    .unwrap_or_else(|p| p);
17            let mut list: Vec<String> = vec![];
18            let end = usize::min(start + 3, n);
19            for i in start..end {
20                if products[i].starts_with(&prefix) {
21                    list.push(products[i].clone());
22                }
23            }
24            res.push(list);
25        }
26        res
27    }
28}
29
30#[test]
31fn test() {
32    let products = vec_string!["mobile", "mouse", "moneypot", "monitor", "mousepad"];
33    let search_word = "mouse".to_string();
34    let res: Vec<Vec<String>> = vec_vec_string![
35        ["mobile", "moneypot", "monitor"],
36        ["mobile", "moneypot", "monitor"],
37        ["mouse", "mousepad"],
38        ["mouse", "mousepad"],
39        ["mouse", "mousepad"]
40    ];
41    assert_eq!(Solution::suggested_products(products, search_word), res);
42    let products = vec_string!["havana"];
43    let search_word = "havana".to_string();
44    let res: Vec<Vec<String>> = vec_vec_string![
45        ["havana"],
46        ["havana"],
47        ["havana"],
48        ["havana"],
49        ["havana"],
50        ["havana"]
51    ];
52    assert_eq!(Solution::suggested_products(products, search_word), res);
53    let products = vec_string!["bags", "baggage", "banner", "box", "cloths"];
54    let search_word = "bags".to_string();
55    let res: Vec<Vec<String>> = vec_vec_string![
56        ["baggage", "bags", "banner"],
57        ["baggage", "bags", "banner"],
58        ["baggage", "bags"],
59        ["bags"]
60    ];
61    assert_eq!(Solution::suggested_products(products, search_word), res);
62    let products = vec_string!["havana"];
63    let search_word = "tatiana".to_string();
64    let res: Vec<Vec<String>> = vec_vec_string![[], [], [], [], [], [], []];
65    assert_eq!(Solution::suggested_products(products, search_word), res);
66}
rustgym/leetcode/_1268_search_suggestions_system.rs

rustgym/leetcode/
_1268_search_suggestions_system.rs
