LeetCode 1268. 搜索推荐系统
题目描述
题意分析
用户每输入搜索词的一个字符，就按当前完整前缀给出一组推荐：只考虑以该前缀开头的商品，从中取字典序最小的至多三个，按字典序返回。
匹配要求从商品名开头开始，不是任意位置包含搜索片段。没有匹配时也要为这一步保留空列表，因此外层结果的组数必须等于搜索词长度。商品不因被推荐而消耗，同一商品可以出现在多个前缀的结果中。
解法：排序 + 二分定位前缀
核心思路
[!blue]
先把商品名按字典序排序。拥有同一前缀的字符串会连续排列：只要某个字符串在前缀结束前就出现更小或更大的字符，它就会整体排在这一组的前面或后面，不能夹在匹配组内部。因此找到匹配区间的左端后，最前面的至多三个商品就是需要的推荐。
对于当前前缀
prefix，用二分查找第一个不小于它的商品，记为start。任何以prefix开头的商品都不会小于prefix，所以更前面的商品一定不匹配。二分采用左闭右开的范围[left, right)：中点不小于前缀就保留左半含中点，否则排除中点及其左侧。
lowerBound只排除了过小的商品，并没有证明找到的商品真正匹配。它可能只是字典序更大的无关名称，甚至已经等于数组长度，所以收集前仍需检查真实前缀。从
start向后读取，匹配就加入本组，直到已有三个结果或遇到第一个不匹配的商品。由于匹配区间连续，一旦离开就不可能在更后面重新进入，可以立即停止本组。对搜索词的每个前缀重复这一过程，并始终追加一组结果。更长前缀只会缩小候选集合，但无匹配时仍然要保留对应空组。排序会重新排列输入商品数组，商品字符串本身不变。
解题步骤
- 按字典序对
products排序，创建外层结果列表。- 逐次扩展搜索前缀，包含从首字符到当前字符的全部内容。
- 二分找到第一个不小于当前前缀的商品下标。
- 从该位置开始，检查是否以当前前缀开头，按顺序收集至多三个商品；首个不匹配项出现时停止。
- 把本轮结果加入外层列表，即使它为空也保留。
- 全部字符处理完后返回各个前缀对应的推荐列表。
代码实现
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;
}
}
import "sort"
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(NL log(N + 1) + M² log(N + 1))，其中N为商品数，L为最长商品长度，M为搜索词长度。排序比较最多读取L个字符；长度为p的前缀查询需O(p log(N + 1))，累加所有前缀长度得到二次项，也涵盖 Java 创建前缀副本的开销。- 空间复杂度：不计输出，Java 排序与前缀缓冲为
O(N + M)，Go 排序栈为O(log(N + 1))。每轮结果最多保存三个商品引用，总输出为O(M)。
关键点总结
[!green]
- 字典序排序使同前缀商品形成连续区间，并直接决定推荐次序。
- 二分定位的是可能起点，前缀校验负责确认匹配，两者不能互相替代。
- 从匹配区间左端取前三个，既满足上限也保证字典序最小。
- 外层每个位置对应一次输入，不因无匹配而省略结果组。
易错点总结
[!yellow]
- 使用子串包含判断：商品必须以前缀开头，出现在中间不算匹配。
- 认为二分结果一定匹配：第一个不小于前缀的商品仍可能无关，需要再次检查。
- 二分返回数组长度后仍访问商品：这表示没有候选，当前组应为空。
- 找到全部匹配都加入结果：每组最多三个，只保留字典序最小的前三个。
- 没有匹配就不追加当前组：会使后续结果与输入字符的位置错位。
- 忽略字符串比较开销：比较和前缀检查需要逐字符进行，不能无条件当成常数时间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | Trie可定位每个查询前缀，本题还需返回该前缀下字典序最小的至多三个产品。 |
| 745. 前缀和后缀搜索 | 困难 | 原题同时筛前后缀并按最大下标选择，本题只筛前缀并按字典序选择。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！