1268. 搜索推荐系统
题目描述
输入字符串数组 products 和字符串 searchWord。
用户依次键入 searchWord 的每个字母。每键入一个字母后，设当前已键入的部分为前缀，从 products 中找出以这个前缀开头的产品，推荐其中字典序最小的至多 3 个，按字典序排列。没有匹配时推荐列表为空。
返回一个二维列表，第 i 项是键入前 i + 1 个字母后的推荐列表。
示例 1
输入：products = ["mobile","mouse","moneypot","monitor","mousepad"] searchWord = "mouse" 输出：[["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
解释：排序后键入 m、mo 时推荐前三个；键入 mou 及以后只有 mouse 和 mousepad 匹配。
示例 2
输入：products = ["havana"], searchWord = "havana" 输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
解释：每个前缀都只匹配 havana。
数据范围
1 <= products.length <= 10001 <= Σ products[i].length <= 2 * 10^4products[i]只含小写英文字母。1 <= searchWord.length <= 1000searchWord只含小写英文字母。
解题思路：排序 + 二分查找
先把 products 按字典序排序，以同一前缀开头的单词在排序后是连续的一段，而且这一段从“第一个 ≥ 前缀的单词”开始。所以每个前缀只需二分查找 lower_bound 位置 lo，然后看 products[lo..lo+2] 中哪些真的以前缀开头。
为什么正确
二分时 products[0..lo-1] 都 < prefix，products[hi..] 都 ≥ prefix；结束时 lo 是第一个 ≥ prefix 的位置。
复杂度分析
排序 O(n log n · L)，每个前缀二分 O(log n · L)，总计 O((n + m) log n · L)；空间 O(1)（不计排序和输出）。
易错点
lo 之后的 3 个单词不一定都以前缀开头，必须逐个检查；lo + 3 可能越界。没有任何匹配时也要放一个空列表。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def suggestedProducts(self, products, searchWord):
products.sort()
res, prefix = [], ""
for c in searchWord:
prefix += c
lo, hi = 0, len(products)
while lo < hi:
mid = (lo + hi) // 2
if products[mid] < prefix:
lo = mid + 1
else:
hi = mid
res.append([w for w in products[lo:lo + 3] if w.startswith(prefix)])
return resclass Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> res = new ArrayList<>(); String prefix = "";
for (char c : searchWord.toCharArray()) {
prefix += c;
int lo = 0, hi = products.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (products[mid].compareTo(prefix) < 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
List<String> cur = new ArrayList<>();
for (int k = lo; k < lo + 3 && k < products.length; k++)
if (products[k].startsWith(prefix)) cur.add(products[k]);
res.add(cur);
}
return res;
}
}class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<vector<string>> res; string prefix = "";
for (char c : searchWord) {
prefix += c;
int lo = 0, hi = products.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (products[mid] < prefix) {
lo = mid + 1;
} else {
hi = mid;
}
}
vector<string> cur;
for (int k = lo; k < lo + 3 && k < (int)products.size(); k++)
if (products[k].compare(0, prefix.size(), prefix) == 0) cur.push_back(products[k]);
res.push_back(cur);
}
return res;
}
};func suggestedProducts(products []string, searchWord string) [][]string {
sort.Strings(products)
res, prefix := [][]string{}, ""
for _, c := range searchWord {
prefix += string(c)
lo, hi := 0, len(products)
for lo < hi {
mid := (lo + hi) / 2
if products[mid] < prefix {
lo = mid + 1
} else {
hi = mid
}
}
cur := []string{}
for k := lo; k < lo+3 && k < len(products); k++ {
if strings.HasPrefix(products[k], prefix) { cur = append(cur, products[k]) }
}
res = append(res, cur)
}
return res
}var suggestedProducts = function(products, searchWord) {
products.sort();
const res = []; 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;
}
}
res.push(products.slice(lo, lo + 3).filter(w => w.startsWith(prefix)));
}
return res;
};function suggestedProducts(products: string[], searchWord: string): string[][] {
products.sort();
const res: 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;
}
}
res.push(products.slice(lo, lo + 3).filter(w => w.startsWith(prefix)));
}
return res;
}其他解法
二分方法利用“排序后共享前缀的字符串连续排列”，每个前缀二分一次即可，不需要额外结构；字典树在每个前缀结点预先存好前 3 个结果，查询最快但占用更多空间。
解法 2：排序 + 字典树 时间 O(n log n · L + 字符总数)，空间 O(字符总数)
先把产品按字典序排序，再依次插入字典树。插入时在路径上的每个结点记录至多 3 个产品：因为产品已经有序，先到达的 3 个就是这个前缀下字典序最小的 3 个。查询时沿着 searchWord 一个字符一个字符往下走，每走一步输出当前结点记录的列表；一旦走到不存在的分支，后面全部输出空列表。
每输入一个字符只需往下走一步，贴近真实搜索框的实时联想，也能预先建好后服务大量查询。建树和存储的开销比二分大，只查一个词时并不划算。
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
children = [{}]
top = [[]]
for w in products:
node = 0
for c in w:
if c not in children[node]:
children[node][c] = len(children)
children.append({})
top.append([])
node = children[node][c]
if len(top[node]) < 3:
top[node].append(w)
res = []
node = 0
for c in searchWord:
node = children[node].get(c, -1) if node >= 0 else -1
res.append(top[node] if node >= 0 else [])
return resclass Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<int[]> children = new ArrayList<>();
List<List<String>> top = new ArrayList<>();
int[] root = new int[26];
Arrays.fill(root, -1);
children.add(root);
top.add(new ArrayList<>());
for (String w : products) {
int node = 0;
for (int k = 0; k < w.length(); k++) {
int c = w.charAt(k) - 'a';
if (children.get(node)[c] < 0) {
children.get(node)[c] = children.size();
int[] fresh = new int[26];
Arrays.fill(fresh, -1);
children.add(fresh);
top.add(new ArrayList<>());
}
node = children.get(node)[c];
if (top.get(node).size() < 3) top.get(node).add(w);
}
}
List<List<String>> res = new ArrayList<>();
int node = 0;
for (int k = 0; k < searchWord.length(); k++) {
if (node >= 0) node = children.get(node)[searchWord.charAt(k) - 'a'];
res.add(node >= 0 ? new ArrayList<>(top.get(node)) : new ArrayList<>());
}
return res;
}
}class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<array<int, 26>> children(1);
children[0].fill(-1);
vector<vector<int>> top(1);
for (int i = 0; i < (int)products.size(); i++) {
int node = 0;
for (char ch : products[i]) {
int c = ch - 'a';
if (children[node][c] < 0) {
children[node][c] = children.size();
children.push_back({});
children.back().fill(-1);
top.push_back({});
}
node = children[node][c];
if (top[node].size() < 3) top[node].push_back(i);
}
}
vector<vector<string>> res;
int node = 0;
for (char ch : searchWord) {
if (node >= 0) node = children[node][ch - 'a'];
vector<string> cur;
if (node >= 0) {
for (int i : top[node]) cur.push_back(products[i]);
}
res.push_back(cur);
}
return res;
}
};func suggestedProducts(products []string, searchWord string) [][]string {
sort.Strings(products)
children := [][26]int{{}}
top := [][]string{{}}
for _, w := range products {
node := 0
for i := 0; i < len(w); i++ {
c := w[i] - 'a'
if children[node][c] == 0 {
children[node][c] = len(children)
children = append(children, [26]int{})
top = append(top, []string{})
}
node = children[node][c]
if len(top[node]) < 3 {
top[node] = append(top[node], w)
}
}
}
res := [][]string{}
node := 0
for i := 0; i < len(searchWord); i++ {
if node >= 0 {
node = children[node][searchWord[i]-'a']
if node == 0 {
node = -1
}
}
if node >= 0 {
res = append(res, append([]string{}, top[node]...))
} else {
res = append(res, []string{})
}
}
return res
}var suggestedProducts = function(products, searchWord) {
products.sort();
const children = [new Map()];
const top = [[]];
for (const w of products) {
let node = 0;
for (const c of w) {
if (!children[node].has(c)) {
children[node].set(c, children.length);
children.push(new Map());
top.push([]);
}
node = children[node].get(c);
if (top[node].length < 3) top[node].push(w);
}
}
const res = [];
let node = 0;
for (const c of searchWord) {
if (node >= 0) node = children[node].has(c) ? children[node].get(c) : -1;
res.push(node >= 0 ? top[node].slice() : []);
}
return res;
};function suggestedProducts(products: string[], searchWord: string): string[][] {
products.sort();
const children: Map<string, number>[] = [new Map()];
const top: string[][] = [[]];
for (const w of products) {
let node = 0;
for (const c of w) {
if (!children[node].has(c)) {
children[node].set(c, children.length);
children.push(new Map());
top.push([]);
}
node = children[node].get(c)!;
if (top[node].length < 3) top[node].push(w);
}
}
const res: string[][] = [];
let node = 0;
for (const c of searchWord) {
if (node >= 0) node = children[node].has(c) ? children[node].get(c)! : -1;
res.push(node >= 0 ? top[node].slice() : []);
}
return res;
}