Question

1268. 搜索推荐系统

English Version

题目描述

给你一个产品数组 products 和一个字符串 searchWord ，products  数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

 

示例 1：

输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2：

输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：

输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：

输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]

 

提示：

• 1 <= products.length <= 1000
• 1 <= Σ products[i].length <= 2 * 10^4
• products[i] 中所有的字符都是小写英文字母。
• 1 <= searchWord.length <= 1000
• searchWord 中所有字符都是小写英文字母。

解法

方法一：排序 + 前缀树

题目要求在输入 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，按字典序返回最小的三个。

找前缀相同的产品，可以使用前缀树；而要返回字典序最小的三个产品，我们可以先对 products 数组进行排序，然后将排序后的数组下标存入前缀树中。

前缀树的每个节点维护以下信息：

• children：这是一个长度为 $26$ 的数组，用于存储当前节点的子节点，children[i] 表示当前节点的子节点中字符为 i + 'a' 的节点。
• v：这是一个数组，用于存储当前节点的子节点中的字符在 products 数组中的下标，最多存储三个下标。

搜索时，我们从前缀树的根节点开始，找到每一个前缀对应的下标数组，将其存入结果数组中。最后只需要将每个下标数组中的下标对应到 products 数组中即可。

时间复杂度 $O(L \times \log n + m)$，空间复杂度 $O(L)$。其中 $L$ 是 products 数组所有字符串的长度之和，而 $n$ 和 $m$ 分别是 products 数组的长度和 searchWord 的长度。

class Trie:
  def __init__(self):
    self.children: List[Union[Trie, None]] = [None] * 26
    self.v: List[int] = []

  def insert(self, w, i):
    node = self
    for c in w:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
      if len(node.v) < 3:
        node.v.append(i)

  def search(self, w):
    node = self
    ans = [[] for _ in range(len(w))]
    for i, c in enumerate(w):
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        break
      node = node.children[idx]
      ans[i] = node.v
    return ans


class Solution:
  def suggestedProducts(
    self, products: List[str], searchWord: str
  ) -> List[List[str]]:
    products.sort()
    trie = Trie()
    for i, w in enumerate(products):
      trie.insert(w, i)
    return [[products[i] for i in v] for v in trie.search(searchWord)]

class Trie {
  Trie[] children = new Trie[26];
  List<Integer> v = new ArrayList<>();

  public void insert(String w, int i) {
    Trie node = this;
    for (int j = 0; j < w.length(); ++j) {
      int idx = w.charAt(j) - 'a';
      if (node.children[idx] == null) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
      if (node.v.size() < 3) {
        node.v.add(i);
      }
    }
  }

  public List<Integer>[] search(String w) {
    Trie node = this;
    int n = w.length();
    List<Integer>[] ans = new List[n];
    Arrays.setAll(ans, k -> new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      int idx = w.charAt(i) - 'a';
      if (node.children[idx] == null) {
        break;
      }
      node = node.children[idx];
      ans[i] = node.v;
    }
    return ans;
  }
}

class Solution {
  public List<List<String>> suggestedProducts(String[] products, String searchWord) {
    Arrays.sort(products);
    Trie trie = new Trie();
    for (int i = 0; i < products.length; ++i) {
      trie.insert(products[i], i);
    }
    List<List<String>> ans = new ArrayList<>();
    for (var v : trie.search(searchWord)) {
      List<String> t = new ArrayList<>();
      for (int i : v) {
        t.add(products[i]);
      }
      ans.add(t);
    }
    return ans;
  }
}

class Trie {
public:
  void insert(string& w, int i) {
    Trie* node = this;
    for (int j = 0; j < w.size(); ++j) {
      int idx = w[j] - 'a';
      if (!node->children[idx]) {
        node->children[idx] = new Trie();
      }
      node = node->children[idx];
      if (node->v.size() < 3) {
        node->v.push_back(i);
      }
    }
  }

  vector<vector<int>> search(string& w) {
    Trie* node = this;
    int n = w.size();
    vector<vector<int>> ans(n);
    for (int i = 0; i < w.size(); ++i) {
      int idx = w[i] - 'a';
      if (!node->children[idx]) {
        break;
      }
      node = node->children[idx];
      ans[i] = move(node->v);
    }
    return ans;
  }

private:
  vector<Trie*> children = vector<Trie*>(26);
  vector<int> v;
};

class Solution {
public:
  vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
    sort(products.begin(), products.end());
    Trie* trie = new Trie();
    for (int i = 0; i < products.size(); ++i) {
      trie->insert(products[i], i);
    }
    vector<vector<string>> ans;
    for (auto& v : trie->search(searchWord)) {
      vector<string> t;
      for (int i : v) {
        t.push_back(products[i]);
      }
      ans.push_back(move(t));
    }
    return ans;
  }
};

type Trie struct {
  children [26]*Trie
  v    []int
}

func newTrie() *Trie {
  return &Trie{}
}
func (this *Trie) insert(w string, i int) {
  node := this
  for _, c := range w {
    c -= 'a'
    if node.children[c] == nil {
      node.children[c] = newTrie()
    }
    node = node.children[c]
    if len(node.v) < 3 {
      node.v = append(node.v, i)
    }
  }
}

func (this *Trie) search(w string) [][]int {
  node := this
  n := len(w)
  ans := make([][]int, n)
  for i, c := range w {
    c -= 'a'
    if node.children[c] == nil {
      break
    }
    node = node.children[c]
    ans[i] = node.v
  }
  return ans
}

func suggestedProducts(products []string, searchWord string) (ans [][]string) {
  sort.Strings(products)
  trie := newTrie()
  for i, w := range products {
    trie.insert(w, i)
  }
  for _, v := range trie.search(searchWord) {
    t := []string{}
    for _, i := range v {
      t = append(t, products[i])
    }
    ans = append(ans, t)
  }
  return
}