跳至主要內容

1268. 搜索推荐系统

1268. 搜索推荐系统

🟠   🔖  字典树 数组 字符串 二分查找 排序 堆（优先队列）  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character ofsearchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].

After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].

After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2:

Input: products = ["havana"], searchWord = "havana"

Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Explanation: The only word "havana" will be always suggested while typing the search word.

Constraints:

  • 1 <= products.length <= 1000
  • 1 <= products[i].length <= 3000
  • 1 <= sum(products[i].length) <= 2 * 10^4
  • All the strings of products are unique.
  • products[i] consists of lowercase English letters.
  • 1 <= searchWord.length <= 1000
  • searchWord consists of lowercase English letters.

题目大意

给你一个产品数组 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 中所有字符都是小写英文字母。

解题思路

  1. 对所有产品进行字典序排序。

  2. 构建字典树：

    • 插入每个产品到字典树中。
    • 同时在每个节点维护一个最多 3 个的候选列表。

  3. 搜索前缀：

    • 遍历 searchWord 的每个字符，在字典树中查找对应节点。
    • 返回节点中的候选列表。

  4. 返回结果：

    • 将每个前缀对应的候选列表加入结果。

复杂度分析

  • 时间复杂度：O(n * L + m)，其中 L 是平均字符串长度， n 是 products 的长度，m 是搜索字符串的长度。
    • 构建字典树：每个字符串插入 O(L)，复杂度为 O(n * L)。
    • 搜索：遍历 searchWord 的每个字符 O(m)，每次查找候选列表 O(3)，复杂度为 O(m)。
    • 总复杂度：O(n * L + m)。
  • 空间复杂度：O(n * L)，字典树占用的空间。

代码

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function (products, searchWord) {
	// 对 products 进行字典序排序
	products.sort();

	// 构建字典树
	let dict = {};
	for (let word of products) {
		let cur = dict;
		for (let char of word) {
			if (!cur[char]) {
				cur[char] = { suggest: [] };
			}
			cur = cur[char];
			if (cur.suggest.length < 3) {
				cur.suggest.push(word);
			}
		}
		cur.isEnd = true;
	}

	// 搜索前缀
	let res = [],
		cur = dict;
	for (let char of searchWord) {
		if (cur) {
			cur = cur[char];
		}
		res.push(cur ? cur.suggest : []);
	}

	return res;
};
Copyright © 2024 2xiao