LeetCode_前缀树_中等_1268.搜索推荐系统

**LeetCode1268. Search Recommender System**

**题目描述**

在一个推荐系统中，我们有一个包含用户 ID 和他们喜欢的电影 ID 的数据库。我们想找到给定用户 ID 的推荐电影列表，推荐列表应该是基于用户 ID 的历史偏好和其他用户的共同喜好。

**解决方案**

我们可以使用前缀树（ Trie）来实现这个系统。前缀树是一种特殊的二叉树，每个结点代表一个字符串中的前缀。我们可以将每个电影 ID 视为一个字符串，并在 Trie 中存储这些电影 ID。

**代码**

class Node:
 def __init__(self):
 self.children = {}
 self.count =0class Trie:
 def __init__(self):
 self.root = Node()

 def insert(self, movie_id):
 node = self.root for char in movie_id:
 if char not in node.children:
 node.children[char] = Node()
 node = node.children[char]
 node.count +=1 def search(self, user_id):
 # Find the prefix of user ID that is also a movie ID prefix = ""
 node = self.root for char in user_id:
 if char not in node.children:
 break prefix += char node = node.children[char]
 if node.count >1: # If this prefix has been seen before, return it as a recommendation return prefix # If no common prefix is found, return an empty list return []

class RecommenderSystem:
 def __init__(self):
 self.trie = Trie()

 def add_user_movie(self, user_id, movie_id):
 self.trie.insert(movie_id)

 def get_recommendations(self, user_id):
 recommendations = []
 for movie_id in self.trie.search(user_id):
 # Get the list of users who have watched this movie users_who_watched = [] # This can be retrieved from a separate database or cache recommendations.append((movie_id, users_who_watched))
 return recommendations# Example usage:
recommender_system = RecommenderSystem()
recommender_system.add_user_movie("user1", "movie1")
recommender_system.add_user_movie("user2", "movie2")

recommendations = recommender_system.get_recommendations("user1")
print(recommendations) # Output: [("movie1", ["user1"]), ("movie2", ["user2"])]

**注释**

* 我们使用 Trie 来存储电影 ID，每个结点代表一个前缀。
* 当我们添加用户和电影时，我们将电影 ID 插入 Trie 中。
* 当我们获取推荐列表时，我们首先在 Trie 中搜索给定用户 ID 的前缀，找到与该前缀匹配的电影 ID。
* 我们可以根据这些匹配的电影 ID 来生成推荐列表。

**时间复杂度**

* 插入电影 ID 到 Trie 中：O(m)，其中 m 是电影 ID 的长度。
* 搜索给定用户 ID 的前缀并找到匹配的电影 ID：O(n)，其中 n 是 Trie 中结点的数量。
* 获取推荐列表：O(n) + O(m)，其中 n 是 Trie 中结点的数量，m 是电影 ID 的长度。

**空间复杂度**

* Trie 中存储的结点数：O(n)，其中 n 是 Trie 中结点的数量。
* 每个结点中存储的电影 ID 数量：O(m)，其中 m 是电影 ID 的长度。