里程商城为了方便客户更快速查找到所需商品,希望实现一个根据用户输入,前缀匹配商品名的功能,用户可能输入多个关键词,则每个关键词分别进行匹配,分别输出结果。现给定商品名称数组、用户输入的关键词数组,输出每个关键词的匹配结果。(待查询的商品信息可能非常多) 输入:["huawei phone","huawei router","apple iphone","xiaomi mix"],["huawei", "apple"] 返回值:[["huawei phone","huawei router"],["apple iphone"]] 备注:字典dict及被搜索的字符串中都只包含小写字母与空格。 必须是前缀匹配,例如 "iphone" 并不会命中 "apple iphone" 用Trie树实现
时间: 2023-02-16 10:23:54 浏览: 69
可以使用 Trie 树来实现这个功能。首先,将所有商品名称插入到 Trie 树中,然后对于每个关键词,在 Trie 树中查找包含该关键词的前缀的所有商品名称。最后,将每个关键词的匹配结果放入一个数组中并返回。
代码如下:
```
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
self.word = ""
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
node.word = word
def search(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return []
node = node.children[char]
return self._find_all_words(node)
def _find_all_words(self, node):
words = []
if node.is_word:
words.append(node.word)
for child in node.children.values():
words.extend(self._find_all_words(child))
return words
def search_products(products, keywords):
trie = Trie()
for product in products:
trie.insert(product)
result = []
for keyword in keywords:
result.append(trie.search(keyword))
return result
```
输入:["huawei phone","huawei router","apple iphone","xiaomi mix"],["huawei", "apple"]
返回值:[["huawei phone","huawei router"],["apple iphone"]]