Rubrik电面挂经

略有些可爱的三哥
先介绍了一下project 然后coderpad做题

Trie的延伸题 不知道LC有没有 我没刷过Trie的题所以不知道题号。。。

given a bag of words

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

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

ccurence of this key}}}


完全没刷trie的任何题 所以各种懵逼。。。

move on move on

这道题在 LC 上没见过，不过如果要做的话应该是在 TrieNode 上添加一个记录单词剩下长度的属性，试一下...

1. from collections import defaultdict
   
2. 
   
3. class TrieNode(object):
   
4.    
   
5.     def __init__(self):
   
6.         self.children = {}
   
7.         self.value = defaultdict(lambda:0)
   
8. 
   
9. class Trie(object):
   
10.    
    
11.     def __init__(self):
    
12.         self.root = TrieNode()
    
13.    
    
14.     def add(self,word):
    
15.         curr = self.root
    
16.         n = len(word)
    
17.         
    
18.         for ch in word:
    
19.             if ch not in curr.children:
    
20.                 curr.children[ch] = TrieNode()
    
21.             curr = curr.children[ch]
    
22.             curr.value[n-1]+=1
    
23.             n-=1
    
24.    
    
25.     def search(self, key):
    
26.         curr = self.root
    
27.         
    
28.         for ch in key:
    
29.             if ch.isalpha():
    
30.                 if ch not in curr.children:
    
31.                     return False
    
32.                
    
33.                 curr = curr.children[ch]
    
34.             else:
    
35.                 # for digit
    
36.                 return curr.value[int(ch)]==1
    
37.         
    
38.         return False
    
39.         
    
40. if __name__ == '__main__':
    
41.     trie = Trie()
    
42.     words = ['apple','baby','ball','amz']
    
43.     for word in words:
    
44.         trie.add(word)
    
45. 
    
46.     assert trie.search("ap3")==True
    
47.     assert trie.search("ba2")==False
    
48.     assert trie.search("a2")==True
    
49.     assert trie.search("bab0")==False

复制代码