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 <= 10001 <= products[i].length <= 30001 <= sum(products[i].length) <= 2 * 104- All the strings of
productsare unique. products[i]consists of lowercase English letters.1 <= searchWord.length <= 1000searchWordconsists of lowercase English letters.
class Trie:
def __init__(self):
self.children: List[Union[Trie, None]] = [None] * 26
self.v: List[int] = []
def insert(self, w, i):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
if len(node.v) < 3:
node.v.append(i)
def search(self, w):
node = self
ans = [[] for _ in range(len(w))]
for i, c in enumerate(w):
idx = ord(c) - ord('a')
if node.children[idx] is None:
break
node = node.children[idx]
ans[i] = node.v
return ans
class Solution:
def suggestedProducts(
self, products: List[str], searchWord: str
) -> List[List[str]]:
products.sort()
trie = Trie()
for i, w in enumerate(products):
trie.insert(w, i)
return [[products[i] for i in v] for v in trie.search(searchWord)]class Trie {
Trie[] children = new Trie[26];
List<Integer> v = new ArrayList<>();
public void insert(String w, int i) {
Trie node = this;
for (int j = 0; j < w.length(); ++j) {
int idx = w.charAt(j) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
if (node.v.size() < 3) {
node.v.add(i);
}
}
}
public List<Integer>[] search(String w) {
Trie node = this;
int n = w.length();
List<Integer>[] ans = new List[n];
Arrays.setAll(ans, k -> new ArrayList<>());
for (int i = 0; i < n; ++i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
break;
}
node = node.children[idx];
ans[i] = node.v;
}
return ans;
}
}
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
Trie trie = new Trie();
for (int i = 0; i < products.length; ++i) {
trie.insert(products[i], i);
}
List<List<String>> ans = new ArrayList<>();
for (var v : trie.search(searchWord)) {
List<String> t = new ArrayList<>();
for (int i : v) {
t.add(products[i]);
}
ans.add(t);
}
return ans;
}
}class Trie {
public:
void insert(string& w, int i) {
Trie* node = this;
for (int j = 0; j < w.size(); ++j) {
int idx = w[j] - 'a';
if (!node->children[idx]) {
node->children[idx] = new Trie();
}
node = node->children[idx];
if (node->v.size() < 3) {
node->v.push_back(i);
}
}
}
vector<vector<int>> search(string& w) {
Trie* node = this;
int n = w.size();
vector<vector<int>> ans(n);
for (int i = 0; i < w.size(); ++i) {
int idx = w[i] - 'a';
if (!node->children[idx]) {
break;
}
node = node->children[idx];
ans[i] = move(node->v);
}
return ans;
}
private:
vector<Trie*> children = vector<Trie*>(26);
vector<int> v;
};
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
Trie* trie = new Trie();
for (int i = 0; i < products.size(); ++i) {
trie->insert(products[i], i);
}
vector<vector<string>> ans;
for (auto& v : trie->search(searchWord)) {
vector<string> t;
for (int i : v) {
t.push_back(products[i]);
}
ans.push_back(move(t));
}
return ans;
}
};type Trie struct {
children [26]*Trie
v []int
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(w string, i int) {
node := this
for _, c := range w {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
if len(node.v) < 3 {
node.v = append(node.v, i)
}
}
}
func (this *Trie) search(w string) [][]int {
node := this
n := len(w)
ans := make([][]int, n)
for i, c := range w {
c -= 'a'
if node.children[c] == nil {
break
}
node = node.children[c]
ans[i] = node.v
}
return ans
}
func suggestedProducts(products []string, searchWord string) (ans [][]string) {
sort.Strings(products)
trie := newTrie()
for i, w := range products {
trie.insert(w, i)
}
for _, v := range trie.search(searchWord) {
t := []string{}
for _, i := range v {
t = append(t, products[i])
}
ans = append(ans, t)
}
return
}