LeetCode 1268中等字典树/排序
搜索推荐系统 图解题解
这道题到底在问什么
给定产品数组 products 与搜索词 searchWord。对 searchWord 的每一个前缀,返回字典序最小的、且以该前缀开头的最多 3 个产品。
- 输入
- products=[mobile,mouse,monitor,mousepad], searchWord=mouse
- 输出
- 逐前缀推荐,从 mobile/monitor/mouse 收窄到 mouse/mousepad
- 输入
- products=[havana], searchWord=tatiana
- 输出
- 每步都是 []（无匹配）
最优解：一步一步想明白
- 3记住「排序让同前缀的产品连成一段 → 二分定位段首 → 连取前 3 验前缀」。二分只负责快速跳到段首,真正以前缀开头还要再验一下。
- 4先看原始 products:[mobile, mouse, monitor, mousepad],顺序是乱的,mouse 和 mousepad 没挨着,也谈不上「字典序前 3」。
- 5第一步按字典序排序。排完之后,任何一个前缀对应的产品都会落在连续的一段里,而且这一段内部就是字典序。
- 6排序得到 [mobile, monitor, mouse, mousepad]。注意 mouse 和 mousepad 现在挨在一起、且 mouse 在前——后面取「前 3」直接顺着取就行。
- 7排好序后,就开始按 searchWord="mouse" 一个字符一个字符地处理:每多敲一个字符,就多一个更长的前缀,各自去二分定位、取推荐。下面逐个前缀走。
- 8搜索框敲到第 1 个字符 'm',当前前缀变成 "m"。要在排好序的产品里挑出以 "m" 打头、字典序最靠前的最多 3 个。
- 9二分(lower_bound)找第一个不小于 "m" 的位置:i = 0(紫),正好是开头,前面没有要排除的。
- 10从 i 起连着取最多 3 个:mobile、monitor、mouse。逐个验是否真的以 "m" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mobile, monitor, mouse]。
- 11搜索框敲到第 2 个字符 'o',当前前缀变成 "mo"。要在排好序的产品里挑出以 "mo" 打头、字典序最靠前的最多 3 个。
- 12二分(lower_bound)找第一个不小于 "mo" 的位置:i = 0(紫),正好是开头,前面没有要排除的。
- 13从 i 起连着取最多 3 个:mobile、monitor、mouse。逐个验是否真的以 "mo" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mobile, monitor, mouse]。
- 14搜索框敲到第 3 个字符 'u',当前前缀变成 "mou"。要在排好序的产品里挑出以 "mou" 打头、字典序最靠前的最多 3 个。
- 15二分(lower_bound)找第一个不小于 "mou" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mou" 小、不可能以它打头,灰掉排除。
- 16从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mou" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
- 17搜索框敲到第 4 个字符 's',当前前缀变成 "mous"。要在排好序的产品里挑出以 "mous" 打头、字典序最靠前的最多 3 个。
- 18二分(lower_bound)找第一个不小于 "mous" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mous" 小、不可能以它打头,灰掉排除。
- 19从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mous" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
- 20搜索框敲到第 5 个字符 'e',当前前缀变成 "mouse"。要在排好序的产品里挑出以 "mouse" 打头、字典序最靠前的最多 3 个。
- 21二分(lower_bound)找第一个不小于 "mouse" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mouse" 小、不可能以它打头,灰掉排除。
- 22从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mouse" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
- 23回头看 searchWord=mouse 这一路:前缀越长,二分定位的段首越往后挪、推荐越收窄,从 mobile/monitor/mouse 一直收到 mouse/mousepad。每个字符只花一次二分加几次前缀比较,既快又稳。
⚠️ 容易写错的地方
✗ 错：二分定位到 i 就直接取 3 个
✓ 对：取候选后再验是否以前缀开头
二分只保证位置 i 的产品不小于前缀,不保证以前缀开头;前缀比所有匹配项都靠后时,i 会指向一个更大、却不以前缀打头的产品
✗ 错：不排序直接二分
✓ 对：必须先按字典序排序
二分定位和「连续取前 3」都建立在已排序之上,不排序两者都不成立
✗ 错：Java 直接用 binarySearch 的返回值
✓ 对：找不到时它返回负数,要转 i = -i - 1
binarySearch 没命中时返回的是负的插入点减一,直接当下标用会出错或越界
完整代码（Python / C++ / Java）
Python
from typing import List
from bisect import bisect_left
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
ans = []
prefix = ''
for ch in searchWord:
prefix += ch
i = bisect_left(products, prefix)
cur = []
for p in products[i:i+3]:
if p.startswith(prefix):
cur.append(p)
ans.append(cur)
return ansC++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<vector<string>> ans;
string prefix;
for (char c : searchWord) {
prefix.push_back(c);
auto it = lower_bound(products.begin(), products.end(), prefix);
vector<string> cur;
for (int k = 0; it + k != products.end() && k < 3; ++k) {
if ((it + k)->rfind(prefix, 0) == 0) cur.push_back(*(it + k));
}
ans.push_back(cur);
}
return ans;
}
};Java
import java.util.*;
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 i = Arrays.binarySearch(products, p);
if (i < 0) i = -i - 1;
List<String> cur = new ArrayList<>();
for (int k = i; k < products.length && k < i + 3; k++) {
if (!products[k].startsWith(p)) break;
cur.add(products[k]);
}
ans.add(cur);
}
return ans;
}
}复杂度
时间
O(n log n + m log n)
排序 n 个产品 O(n log n);searchWord 长 m,每个前缀二分 O(log n)、再验最多 3 个前缀,合起来约 O(m log n)
空间
O(1) 除输出
原地排序、只用前缀串与几个下标;返回的推荐列表本身另算
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 搜索推荐系统 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用字典树(Trie)做?+
能。把每个产品插入 Trie,每个节点额外维护「经过它的字典序最小的 3 个产品」。查询时沿 searchWord 一路往下走 L 步,每走到一个节点就直接读它存好的前 3 个,查询是 O(L)。排序加二分更短好写;Trie 在「同一份产品反复查很多搜索词」或在线输入时更划算。
为什么用二分,不每个前缀都线性扫一遍?+
排序后用二分能 O(log n) 直接跳到段首,而线性扫每个前缀要 O(n)。searchWord 有 m 个前缀,二分把这部分从 O(m·n) 降到 O(m·log n),产品多时差距很明显。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 搜索推荐系统 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。