1268. Search Suggestions System

LeetCode medium original: C# #array #csharp #graph #leetcode #medium #prefix-sum #search #sort #string

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Вам дан array строк products и string searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикоgraphически минимальных продукта. returnsся список списков предложенных продуктов после ввода каждого символа searchWord.

Example:

Input: products = ["havana"], searchWord = "havana"

Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
        Array.Sort(products);
        var result = new List<IList<string>>();
        var prefix = "";
        foreach (var c in searchWord) {
            prefix += c;
            var suggestions = products.Where(p => p.StartsWith(prefix)).Take(3).ToList();
            result.Add(suggestions);
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<string>> SuggestedProducts(vector<string> products, string searchWord) {
        sort(products.begin(), products.end());
        var result = new List<vector<string>>();
        var prefix = "";
        foreach (var c in searchWord) {
            prefix += c;
            var suggestions = products.Where(p => p.StartsWith(prefix)).Take(3).ToList();
            result.push_back(suggestions);
        }
        return result;
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> result = new ArrayList<>();
        String prefix = "";
        for (char c : searchWord.toCharArray()) {
            prefix += c;
            List<String> suggestions = new ArrayList<>();
            for (String product : products) {
                if (product.startsWith(prefix)) {
                    suggestions.add(product);
                    if (suggestions.size() == 3) break;
                }
            }
            result.add(suggestions);
        }
        return result;
    }
}

JavaScript solution

matched/original

var suggestedProducts = function(products, searchWord) {
    products.sort();
    let result = [];
    let prefix = "";
    for (let char of searchWord) {
        prefix += char;
        let suggestions = products.filter(product => product.startsWith(prefix)).slice(0, 3);
        result.push(suggestions);
    }
    return result;
};

Python solution

matched/original

def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    prefix = ""
    for char in searchWord:
        prefix += char
        suggestions = [product for product in products if product.startswith(prefix)]
        result.append(suggestions[:3])
    return result

Go solution

matched/original

import "sort"

func suggestedProducts(products []string, searchWord string) [][]string {
    sort.Strings(products)
    result := [][]string{}
    prefix := ""
    for _, char := range searchWord {
        prefix += string(char)
        suggestions := []string{}
        for _, product := range products {
            if len(suggestions) == 3 {
                break
            }
            if len(product) >= len(prefix) && product[:len(prefix)] == prefix {
                suggestions = append(suggestions, product)
            }
        }
        result = append(result, suggestions)
    }
    return result
}

Algorithm

Отсортируйте array продуктов.

Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.

Сохраняйте не более трех лексикоgraphически минимальных продуктов для каждого префикса.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.