Pinterest Onsite blacklist 那道题

用trie来做，我用py

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

E_0        ]

我贴一个 和leetcode 208. Implement Trie (Prefix Tree) 类似的解法：

1. class TrieNode(object):
   
2.     def __init__(self):
   
3.         self.end = False
   
4.         self.children = {}
   
5. 
   
6. class searchData(object):
   
7.     def __init__(self):
   
8.         self.root = TrieNode()
   
9. 
   
10.     def buildTrie(self, word_dict):
    
11.         for item in word_dict:
    
12.             curr_node = self.root
    
13. 
    
14.             item_split = item.split(" ")
    
15.             for word in item_split:
    
16.                 if word not in curr_node.children:
    
17.                     curr_node.children[word] = TrieNode()
    
18.                 curr_node = curr_node.children[word]
    
19.             curr_node.end = True
    
20. 
    
21. 
    
22.     def searchWords(self, words):
    
23.         words_split = words.split(" ")
    
24.         curr_node = self.root
    
25. 
    
26.         for item in curr_node.children:
    
27.             print item
    
28. 
    
29.         result = []
    
30.         for i in range(len(words_split)):
    
31.             word = words_split[i]
    
32.             j = i
    
33.             curr_node = self.root
    
34. 
    
35.             while word in curr_node.children:
    
36.                 curr_node = curr_node.children[word]
    
37.                 j += 1
    
38.                 if j<len(words_split):
    
39.                     word = words_split[j]
    
40. 
    
41.                 if curr_node.end:
    
42.                     result.append(" ".join(words_split[i:j]))
    
43.         return result

复制代码

不错不错，赞一下！