针有趣店面挂经

大概写了一下

1. class TrieNode:
   
2.     def __init__(self):
   
3.         self.children = {}
   
4.         self.item = None
   
5. 
   
6. def findMatchedItems(items, query):
   
7.     trie_root = TrieNode()
   
8.     for s, weight in items:
   
9.         words = s.split()
   
10.         trie_node = trie_root
    
11.         for word in words:
    
12.             if word not in trie_node.children:
    
13.                 trie_node.children[word] = TrieNode()
    
14.             trie_node = trie_node.children[word]
    
15.         trie_node.item = (s, weight)
    
16. 
    
17.     query_words = query.split()
    
18.     trie_node = trie_root
    
19.     for word in query_words:
    
20.         if word not in trie_node.children:
    
21.             return []
    
22.         trie_node = trie_node.children[word]
    
23. 
    
24.     result = []
    
25.     stack = [(trie_node)]
    
26.     while stack:
    
27.         node = stack.pop()
    
28.         if node.item:
    
29.             result.append(node.item)
    
30. 
    
31.         for child in node.children:
    
32.             stack.append((node.children[child]))
    
33.     result.sort(key=lambda x: x[1], reverse=True)
    
34.     return result
    
35. 
    
36. 
    
37. 
    
38. items = [
    
39.     ("fried rice", 10000),
    
40.     ("fried rice egg", 500),
    
41.     ("egg rice", 300),
    
42.     ("fried rice pork", 600),
    
43.     ("fried rice chicken", 400),
    
44.     ("fried rice shrimp pineapple", 200)
    
45. ]
    
46. 
    
47. query = "fried rice"
    
48. result = findMatchedItems(items, query)
    
49. print(result)

复制代码