JZX轻语：简
LeetCode 1268 - 搜索推荐系统
发表于2024年07月15日
两种做法：一种是基于字典树，即在原模板代码的基础上，给每一个Trie节点新增一个成员变量candidates，用于存储当前节点对应的前缀中字典序top-3的单词，先将所有的单词加入到Trie树中，后面再按搜索词遍历树，沿着节点将candidates添加到结果中；另一种是基于二分搜索，先对单词列表进行排序，然后枚举搜索词的前缀，使用二分搜索找到第一个大于等于该前缀的单词，然后向后选择三个单词即可。需要注意的是，选择单词时，需要判断是否前缀匹配！如果遇到不匹配的单词，直接跳出循环。
基于字典树的做法：
class Trie:
def __init__(self):
self.child = [None] * 26 # type: list[Optional[Trie]]
self.candidates = [] # 新增成员变量: 存储当前节点对应的前缀中字典序top-3的单词
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
ord_a = ord('a')
root = Trie()
for product in products:
cur = root
for ch in product:
idx = ord(ch) - ord_a
if not cur.child[idx]:
cur.child[idx] = Trie()
cur = cur.child[idx]
if len(cur.candidates) < 3 or product < cur.candidates[2]:
# 该单词是新的top-3单词, 插入到candidates中
# 注意，插入后需要重新排序, 并弹出多余的单词
cur.candidates.append(product)
cur.candidates.sort()
if len(cur.candidates) > 3:
cur.candidates.pop()
ans = []
cur = root
for ch in searchWord:
idx = ord(ch) - ord_a
cur = cur.child[idx]
if cur:
ans.append(cur.candidates)
else: # 未找到前缀, 直接跳出
break
# 如果搜索词长度大于结果长度, 说明提前跳出了, 补齐空列表
ans += [[]] * (len(searchWord) - len(ans))
return ans基于二分搜索的做法：
import bisect
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
ans = []
for i in range(1, len(searchWord) + 1):
key = searchWord[:i]
ip = bisect.bisect_left(products, key)
res = []
for j in range(3):
if ip + j >= len(products) or products[ip + j][:i] != key:
break
res.append(products[ip + j])
ans.append(res)
return ans