发表于 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

• LC 题目链接