题目描述
思路解析动画文字版
记住「排序让同前缀的产品连成一段 → 二分定位段首 → 连取前 3 验前缀」。二分只负责快速跳到段首,真正以前缀开头还要再验一下。
先看原始 products:[mobile, mouse, monitor, mousepad],顺序是乱的,mouse 和 mousepad 没挨着,也谈不上「字典序前 3」。
第一步按字典序排序。排完之后,任何一个前缀对应的产品都会落在连续的一段里,而且这一段内部就是字典序。
排序得到 [mobile, monitor, mouse, mousepad]。注意 mouse 和 mousepad 现在挨在一起、且 mouse 在前——后面取「前 3」直接顺着取就行。
排好序后,就开始按 searchWord="mouse" 一个字符一个字符地处理:每多敲一个字符,就多一个更长的前缀,各自去二分定位、取推荐。下面逐个前缀走。
搜索框敲到第 1 个字符 'm',当前前缀变成 "m"。要在排好序的产品里挑出以 "m" 打头、字典序最靠前的最多 3 个。
二分(lower_bound)找第一个不小于 "m" 的位置:i = 0(紫),正好是开头,前面没有要排除的。
从 i 起连着取最多 3 个:mobile、monitor、mouse。逐个验是否真的以 "m" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mobile, monitor, mouse]。
搜索框敲到第 2 个字符 'o',当前前缀变成 "mo"。要在排好序的产品里挑出以 "mo" 打头、字典序最靠前的最多 3 个。
二分(lower_bound)找第一个不小于 "mo" 的位置:i = 0(紫),正好是开头,前面没有要排除的。
从 i 起连着取最多 3 个:mobile、monitor、mouse。逐个验是否真的以 "mo" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mobile, monitor, mouse]。
搜索框敲到第 3 个字符 'u',当前前缀变成 "mou"。要在排好序的产品里挑出以 "mou" 打头、字典序最靠前的最多 3 个。
二分(lower_bound)找第一个不小于 "mou" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mou" 小、不可能以它打头,灰掉排除。
从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mou" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
搜索框敲到第 4 个字符 's',当前前缀变成 "mous"。要在排好序的产品里挑出以 "mous" 打头、字典序最靠前的最多 3 个。
二分(lower_bound)找第一个不小于 "mous" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mous" 小、不可能以它打头,灰掉排除。
从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mous" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
搜索框敲到第 5 个字符 'e',当前前缀变成 "mouse"。要在排好序的产品里挑出以 "mouse" 打头、字典序最靠前的最多 3 个。
二分(lower_bound)找第一个不小于 "mouse" 的位置:i = 2(紫)。它前面的 mobile、monitor 字典序都比 "mouse" 小、不可能以它打头,灰掉排除。
从 i 起连着取最多 3 个:mouse、mousepad。逐个验是否真的以 "mouse" 开头(排序后匹配项是连续的,碰到第一个不匹配就停)。命中的标绿:推荐 = [mouse, mousepad]。
回头看 searchWord=mouse 这一路:前缀越长,二分定位的段首越往后挪、推荐越收窄,从 mobile/monitor/mouse 一直收到 mouse/mousepad。每个字符只花一次二分加几次前缀比较,既快又稳。
边界:无匹配返回空、不足 3 个就给实际数量、空了之后更长前缀也空。
两个高频追问:可用 Trie 节点存前 3 做到查询 O(L);二分比线性扫快在对数定位。
参考代码
from typing import Listfrom bisect import bisect_leftclass 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 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) 除输出，原地排序、只用前缀串与几个下标;返回的推荐列表本身另算
易错点
面试追问把动画讲成自己的话
追问能不能用字典树(Trie)做?
追问为什么用二分,不每个前缀都线性扫一遍?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词搜索 II
LeetCode 212 · 困难 · 沿着 字典树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题