Pinterest新鲜上门挂经

落魄酸丁 发表于 2018-10-24 02:00
楼主什么时候面的啊？

昨天紫薯紫薯紫薯

Tyrant89 发表于 2018-10-24 07:16
就是建立个Trie，但不同的是我TRie里面的每个元素是单词不是字母

是的我也是用的word Trie~

FML 发表于 2018-10-24 07:35
这题是不是就是建树的意思呀

不会出现的，就是直接上级，一个多叉树

pandami 发表于 2018-10-24 07:29
第三轮是说有很多string求最长共同prefix？

是的是的～

泡芙小姐的金鱼 发表于 2018-10-24 11:36
是的我也是用的word Trie~

想请教一下要是对blacklist建word trie的话，应该还需要对Pintext里的每个单词作为开头search trie吧？

楼主是网申还是怎样的啊？

1. import unittest
   
2. 
   
3. class TrieNode:
   
4.     def __init__(self):
   
5.         self.table = dict()
   
6.         self.phraseEnd = False
   
7. 
   
8. 
   
9. class Trie:
   
10.     def __init__(self):
    
11.         self.root = TrieNode()
    
12. 
    
13.     def insertPhrase(self, phrase):
    
14.         node = self.root
    
15.         words = phrase.split(' ')
    
16. 
    
17.         for word in words:
    
18.             if word not in node.table:
    
19.                 node.table[word] = TrieNode()
    
20.             node = node.table[word]
    
21. 
    
22.         node.phraseEnd = True
    
23. 
    
24.     def search(self, words):
    
25.         node = self.root
    
26. 
    
27.         for word in words:
    
28.             if node.phraseEnd:
    
29.                 return True
    
30.             if word not in node.table:
    
31.                 return False
    
32.             node = node.table[word]
    
33.         return node.phraseEnd
    
34. 
    
35. 
    
36. class Solution:
    
37.     def isSafe(self, blackList, pintext):
    
38.         if not blackList or not pintext:
    
39.             return True
    
40.         
    
41.         trie = Trie()
    
42.         for phrase in blackList:
    
43.             trie.insertPhrase(phrase)
    
44.         
    
45.         pintextWords = pintext.split(" ")
    
46.         for i in range(len(pintextWords)):
    
47.             if trie.search(pintextWords[i:]):
    
48.                 return False
    
49.         return True
    
50. 
    
51. class SolutionTest(unittest.TestCase):
    
52.     def testIsSafe(self):
    
53.         sol = Solution()
    
54.         blackList = ["machine guns", "world war i"]
    
55.         self.assertFalse(sol.isSafe(blackList, "i love world war i"))
    
56.         self.assertTrue(sol.isSafe(blackList, "world war ii"))
    
57. 
    
58. if __name__=='__main__':
    
59.     unittest.main()

复制代码

补充内容 (2018-10-24 14:13):
试着用Trie的思路做了第一个pintext safe的问题

请问下lz 可以用白板写思路么，然后laptop coding。还想问下每轮有多少时间是在问简历或者bq的？谢谢！

泡芙小姐的金鱼 发表于 2018-10-24 11:36
不会出现的，就是直接上级，一个多叉树

谢谢楼主，祝你offer多多

金妮韦崽 发表于 2018-10-24 13:19
楼主是网申还是怎样的啊？

朋友内推的～