LeetCode 1268. 搜索推荐系统

2026-06-24 HGNULB 约 7 分钟

文章信息 8 个分类 6 个标签

分类

LeetCode CodeTop 中等未解决 2-5 字节跳动腾讯 LeetCode 75

题目描述

✅ 1268. 搜索推荐系统

题意分析

模拟一个搜索框的联想功能：用户逐个字符输入 searchWord，每敲一个字符就产生一个前缀，系统要为这个前缀返回商品列表里以它开头的、字典序最小的至多三个商品名。输入了几个字符就返回几组结果。

「至多三个」意味着候选不足三个时按实际数量返回，一个都没有时返回空列表而不是缺一项——外层结果的长度必须严格等于 searchWord 的长度。

「字典序最小的三个」要求组内也有序，不能随手挑三个凑数。

前缀之间存在天然的包含关系：第 $i+1$ 个前缀比第 $i$ 个多一个字符，所以它的候选集必然是前一个候选集的子集，只会越缩越小，永远不会有商品退出后又回来。

规模上商品数最多 1000、单词长度最多 3000、总字符数不超过 $2 \times 10^4$，都不大，排序加多次二分绰绰有余。

解法：排序 + 二分定位前缀

核心思路

暴力做法是对每个前缀扫一遍全部商品，挑出匹配的再排序取前三。设商品数为 $n$、平均长度为 $L$、搜索词长为 $m$，代价是 $O(mnL)$ 加上每轮的排序开销。数据量下能过，但把「排序」这件事重复做了 $m$ 次，明显浪费。

瓶颈在于每一轮都要从头筛选并重新排序。而排序其实只需要做一次：一旦 products 按字典序排好，同一个前缀的所有匹配项一定占据一段连续区间。原因是字典序的性质——若 $a \le b \le c$ 且 $a$ 和 $c$ 都以 $p$ 开头，那么 $b$ 必然也以 $p$ 开头，中间不可能夹进一个不匹配的串。

有了连续性，问题就变成「找到这段区间的左端点」。以前缀 $p$ 开头的字符串在字典序上都不小于 $p$ 本身，而所有小于 $p$ 的串一定不以 $p$ 开头，所以区间左端点恰好是「第一个不小于 $p$ 的位置」，用一次二分即可定位。

这里的不变量是：lowerBound(prefix) 返回的下标 $s$ 满足——$[0, s)$ 内的商品全部字典序小于 $p$（从而必定不匹配），$[s, n)$ 内的商品全部不小于 $p$。因此匹配项若存在，必从 $s$ 开始连续排布；从 $s$ 起往后走，遇到的第一个不以 $p$ 开头的商品就是区间右边界，可以立刻停止。

注意二分只保证「不小于」，不保证「匹配」，所以取出的每一项仍要显式校验前缀。而由于只要三个，扫描最多向后走三步就够，整轮的收集是常数次比较。

另一条常见路线是字典树：把商品插入 Trie，每个节点挂上该子树中字典序最小的三个商品，查询时沿着 searchWord 走一遍即可。它更贴近「搜索推荐」的工程原型，复杂度也更优，但排序加二分的写法在面试白板上更短、更不容易写错。

解题步骤

先对 products 整体按字典序排序。这一步是全部后续推理的前提，只做一次，之后再也不排序。

用一个可变缓冲逐字符追加 searchWord，第 $i$ 轮得到长度为 $i+1$ 的前缀。逐步追加而不是每轮重新截取，可以避免重复构造字符串（Go 版直接用切片 searchWord[:i+1]，本身就是零拷贝）。

对当前前缀调 lowerBound：标准的左闭右开二分，条件为 products[mid] >= prefix 时收右界，否则左界跳到 mid + 1，循环终止时 left 就是第一个不小于前缀的位置。用 right = products.length 而不是 length - 1，是为了让「全部商品都小于前缀」时能自然返回 $n$，交给后面的边界判断处理。

从 start 开始向后扫，循环条件同时限制 j < n 和已收集数量小于 3。数量上限写进循环条件，保证最多只看三项。

每项先校验 startsWith(prefix)，不满足就 break 而不是 continue。用 break 是因为连续性保证了后面再也不会有匹配项，继续扫纯属浪费；同时这也顺带处理了 start == n 的情形，循环一次都不进。

每轮把收集到的列表（可能为空）追加进答案。哪怕一个都没找到也要追加空列表，否则返回的组数会少于搜索词长度。

以 products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse" 走一遍：排序后数组是 ["mobile","moneypot","monitor","mouse","mousepad"]，下标 0 到 4。

第 1 轮前缀 "m"：二分找第一个不小于 "m" 的位置，"mobile" 已经大于 "m"（前者以后者为前缀且更长），左端点是 0。从下标 0 起收集，mobile、moneypot、monitor 都以 m 开头，凑满三个停下，得到 ["mobile","moneypot","monitor"]。

第 2 轮前缀 "mo"：同样定位到下标 0，收集结果不变，仍是 ["mobile","moneypot","monitor"]。

第 3 轮前缀 "mou"：二分时 "mobile" 的第三个字符 b 小于 u，"moneypot" 和 "monitor" 的第三个字符 n 也小于 u，三者都排在前缀之前；"mouse" 不小于 "mou"，于是左端点是 3。从下标 3 起收集到 mouse 和 mousepad，下标走到 5 越界结束，得到两项。

第 4 轮前缀 "mous"：左端点仍是 3，结果同上。

第 5 轮前缀 "mouse"："mouse" 与前缀相等，二分返回 3；mouse 匹配，mousepad 也以 "mouse" 开头，同样收集到两项。

最终返回五组结果，前两组各三项、后三组各两项，与输入的五个字符一一对应。可以看到候选集随着前缀变长只减不增，正是连续区间不断收窄的表现。

代码实现

// 对每个前缀，只需要找到第一个不小于该前缀的位置，再向后检查最多三个匹配项。
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> answer = new ArrayList<>();
        StringBuilder prefixBuilder = new StringBuilder();

        for (int i = 0; i < searchWord.length(); i++) {
            prefixBuilder.append(searchWord.charAt(i));
            String prefix = prefixBuilder.toString();
            int start = lowerBound(products, prefix);

            List<String> cur = new ArrayList<>();
            for (int j = start; j < products.length && cur.size() < 3; j++) {
                if (!products[j].startsWith(prefix)) {
                    break;
                }
                cur.add(products[j]);
            }
            answer.add(cur);
        }

        return answer;
    }

    private int lowerBound(String[] products, String prefix) {
        int left = 0;
        int right = products.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (products[mid].compareTo(prefix) >= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

// 对每个前缀，只需要找到第一个不小于该前缀的位置，再向后检查最多三个匹配项。
func suggestedProducts(products []string, searchWord string) [][]string {
    sort.Strings(products)
    answer := make([][]string, 0, len(searchWord))

    for i := 0; i < len(searchWord); i++ {
        prefix := searchWord[:i+1]
        start := lowerBoundString(products, prefix)

        cur := make([]string, 0, 3)
        for j := start; j < len(products) && len(cur) < 3; j++ {
            if !hasPrefix(products[j], prefix) {
                break
            }
            cur = append(cur, products[j])
        }
        answer = append(answer, cur)
    }

    return answer
}

func lowerBoundString(products []string, prefix string) int {
    left, right := 0, len(products)
    for left < right {
        mid := left + (right-left)/2
        if products[mid] >= prefix {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func hasPrefix(word string, prefix string) bool {
    return len(word) >= len(prefix) && word[:len(prefix)] == prefix
}

复杂度分析

时间复杂度：$O(n \log n \cdot L + m \cdot (\log n \cdot L + L))$。

空间复杂度：$O(\log n + m)$，排序递归栈与每个前缀的至多三个推荐结果；不计输出时为 $O(\log n)$。

关键点总结

推荐结果要求字典序最小的最多三个商品，先排序可以让候选顺序天然正确。

对每个前缀，只需要找到第一个不小于该前缀的位置，再向后检查最多三个匹配项。

一旦排序数组中的某个商品不再匹配当前前缀，后面的商品也不可能重新成为当前前缀的更小推荐。

易错点总结

二分得到的是第一个不小于前缀的位置，不一定真的匹配前缀。

每个前缀最多返回三个商品，不能把后面所有匹配项都加入。

商品已经排序后，同一前缀的候选按字典序天然有序。

相似题目

题目	难度	考察点
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分确定一段候选区间