algorithms/leetcode/1268-SearchSuggestionsSystem.go at master · freewu/algorithms · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package main

// 1268. Search Suggestions System
// You are given an array of strings products and a string searchWord.

// Design a system that suggests at most three product names from products after each character of searchWord is typed.
// Suggested products should have common prefix with searchWord.
// If there are more than three products with a common prefix return the three lexicographically minimums products.

// Return a list of lists of the suggested products after each character of searchWord is typed.

// Example 1:
// Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
// Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
// Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
// After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
// After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

// Example 2:
// Input: products = ["havana"], searchWord = "havana"
// Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
// Explanation: The only word "havana" will be always suggested while typing the search word.

// Constraints:
//     1 <= products.length <= 1000
//     1 <= products[i].length <= 3000
//     1 <= sum(products[i].length) <= 2 * 10^4
//     All the strings of products are unique.
//     products[i] consists of lowercase English letters.
//     1 <= searchWord.length <= 1000
//     searchWord consists of lowercase English letters.

import "fmt"
import "sort"

func suggestedProducts(products []string, searchWord string) [][]string {
    sort.Strings(products) // Sort the products lexicographically
    res, prefix := make([][]string, len(searchWord)), ""
    // Helper function to check if a string starts with a given prefix
    startsWith := func(s, prefix string) bool {
        if len(s) < len(prefix) {
            return false
        }
        for i := 0; i < len(prefix); i++ {
            if s[i] != prefix[i] {
                return false
            }
        }
        return true
    }
    for i, char := range searchWord {
        prefix += string(char)
        // Binary search for the index of the first product with a prefix >= prefix
        index := sort.SearchStrings(products, prefix)
        // Collect up to three suggested products with the common prefix
        for j := index; j < len(products) && j < index+3; j++ {
            if !startsWith(products[j], prefix) {
                break
            }
            res[i] = append(res[i], products[j])
        }
    }
    return res
}

func suggestedProducts1(products []string, searchWord string) [][]string {
    sort.Strings(products)
    ptr, res := 0, [][]string{}
    for i := 1; i < len(searchWord) + 1; i++ {
        prefix := searchWord[:i]
        for ptr < len(products) && products[ptr] < prefix {
            ptr++
        }
        tmp := []string{}
        for j := ptr; j < min(len(products), ptr + 3); j++ {
            if len(products[j]) >= i && products[j][:i] == prefix {
                tmp = append(tmp, products[j])
            }
        }
        res = append(res, tmp)
    }
    return res
}

func main() {
    // Example 1:
    // Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
    // Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
    // Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
    // After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
    // After typing mou, mous and mouse the system suggests ["mouse","mousepad"].
    fmt.Println(suggestedProducts([]string{"mobile","mouse","moneypot","monitor","mousepad"},"mouse")) // [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
    // Example 2:
    // Input: products = ["havana"], searchWord = "havana"
    // Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
    // Explanation: The only word "havana" will be always suggested while typing the search word.
    fmt.Println(suggestedProducts([]string{"havana"},"havana")) // [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

    fmt.Println(suggestedProducts1([]string{"mobile","mouse","moneypot","monitor","mousepad"},"mouse")) // [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
    fmt.Println(suggestedProducts1([]string{"havana"},"havana")) // [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
}