Search Suggestions System

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        vector<vector<string>> ans;
        ans.reserve(searchWord.size());
        string prefix;
        for (char c : searchWord) {
            prefix.push_back(c);
            auto it = lower_bound(products.begin(), products.end(), prefix);
            vector<string> row;
            for (int k = 0; k < 3 && it + k != products.end(); ++k) {
                const string& p = *(it + k);
                if (p.compare(0, prefix.size(), prefix) != 0) break;
                row.push_back(p);
            }
            ans.push_back(std::move(row));
        }
        return ans;
    }
};

import (
    "sort"
    "strings"
)

func suggestedProducts(products []string, searchWord string) [][]string {
    sort.Strings(products)
    ans := make([][]string, 0, len(searchWord))
    prefix := ""
    for _, c := range searchWord {
        prefix += string(c)
        it := sort.SearchStrings(products, prefix)
        row := []string{}
        for k := 0; k < 3 && it+k < len(products); k++ {
            p := products[it+k]
            if !strings.HasPrefix(p, prefix) {
                break
            }
            row = append(row, p)
        }
        ans = append(ans, row)
    }
    return ans
}

from bisect import bisect_left
from typing import List

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        ans: List[List[str]] = []
        prefix = ""
        for c in searchWord:
            prefix += c
            i = bisect_left(products, prefix)
            row: List[str] = []
            for k in range(3):
                if i + k >= len(products):
                    break
                p = products[i + k]
                if not p.startswith(prefix):
                    break
                row.append(p)
            ans.append(row)
        return ans

function suggestedProducts(products, searchWord) {
    products.sort();
    const ans = [];
    let prefix = "";
    for (const c of searchWord) {
        prefix += c;
        let lo = 0, hi = products.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (products[mid] < prefix) lo = mid + 1;
            else hi = mid;
        }
        const row = [];
        for (let k = 0; k < 3 && lo + k < products.length; k++) {
            const p = products[lo + k];
            if (!p.startsWith(prefix)) break;
            row.push(p);
        }
        ans.push(row);
    }
    return ans;
}

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> ans = new ArrayList<>();
        StringBuilder prefix = new StringBuilder();
        for (char c : searchWord.toCharArray()) {
            prefix.append(c);
            String p = prefix.toString();
            int lo = 0, hi = products.length;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (products[mid].compareTo(p) < 0) lo = mid + 1;
                else hi = mid;
            }
            List<String> row = new ArrayList<>();
            for (int k = 0; k < 3 && lo + k < products.length; k++) {
                String s = products[lo + k];
                if (!s.startsWith(p)) break;
                row.add(s);
            }
            ans.add(row);
        }
        return ans;
    }
}

function suggestedProducts(products: string[], searchWord: string): string[][] {
    products.sort();
    const ans: string[][] = [];
    let prefix = "";
    for (const c of searchWord) {
        prefix += c;
        let lo = 0, hi = products.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (products[mid] < prefix) lo = mid + 1;
            else hi = mid;
        }
        const row: string[] = [];
        for (let k = 0; k < 3 && lo + k < products.length; k++) {
            const p = products[lo + k];
            if (!p.startsWith(prefix)) break;
            row.push(p);
        }
        ans.push(row);
    }
    return ans;
}