Leetcode 336 求教 感觉写了O(n) 可是TLE了

1. class Node:
   
2.     def __init__(self,digit):
   
3.         self.char = digit
   
4.         self.children = {}
   
5.         self.isword = False
   
6.         self.wordidx = None
   
7.         self.word = None
   
8.         self.palinidx = []
   
9. class Trie:
   
10.     def __init__(self):
    
11.         self.head = Node("")
    
12.         self.palindrone = []
    
13.     def insert(self,word,idx):
    
14.         if word == "":
    
15.             self.head.isword = True
    
16.             self.head.wordidx = idx
    
17.             self.head.word = ""
    
18.             return
    
19.         tmp = self.head
    
20.         if self.isplin(word):
    
21.             tmp.palinidx.append(idx)
    
22.         for i in range(len(word)):
    
23.             if word[i] not in tmp.children:
    
24.                 tmp.children[word[i]] = Node(word[i])
    
25.             if self.isplin(word[i::]):
    
26.                 #print(word,word[(i+1)::])
    
27.                 tmp.palinidx.append(idx)
    
28.                 #print(tmp.word,tmp.char,tmp.palinidx)
    
29.             tmp = tmp.children[word[i]]
    
30.         tmp.isword = True
    
31.         tmp.wordidx = idx
    
32.         tmp.word = word
    
33.         if self.isplin(word):
    
34.             self.palindrone.append(idx)
    
35.             
    
36.     def find(self,word):
    
37.         if word == "":
    
38.             return self.palindrone
    
39.         tmp = self.head
    
40.         ans = []
    
41.         if tmp.isword and self.isplin(word):
    
42.             ans.append(tmp.wordidx)
    
43.         for i in range(1,len(word) +1):
    
44.             if word[-i] in tmp.children:
    
45.                 tmp = tmp.children[word[-i]]
    
46.                 if tmp.isword:
    
47.                     if self.isplin(word[-len(word):(-i)]):
    
48.                         ans.append(tmp.wordidx)
    
49.             else:
    
50.                 return ans
    
51.    
    
52.         ans.extend(tmp.palinidx)
    
53.         return ans
    
54.    
    
55.     def isplin(self,w):
    
56. 
    
57.         return w == w[::-1]
    
58.                
    
59.                
    
60. class Solution(object):
    
61.     def palindromePairs(self, words):
    
62.         """
    
63.         :type words: List[str]
    
64.         :rtype: List[List[int]]
    
65.         """
    
66.         MyTrie = Trie()
    
67.         for i in range(len(words)):
    
68.             MyTrie.insert(words[i],i)
    
69.         ans = []
    
70.         for i in range(len(words)):
    
71.             ans = ans + [ [idx,i]  for idx in MyTrie.find(words[i]) if idx != i]
    
72.         return ans
    
73.         
    
74.         

复制代码

写了一个trie 检查了好几遍都觉得是O(n) 不明白为什么TLE
求帮忙

greynut 发表于 2018-2-17 02:36
那请问有神么可以改进的地方吗？

但是我以为lc已经优化过，时间都是跟同种语言比的？

我试着优化了一下，感觉Python用普通Trie应该是没有办法Accept的，因为这道题目的输入的字符串都很长。

找了组LeetCode的测试数据，大概长这样：

1. "hdhbaggbjiagiihgidda"
   
2. "jj"
   
3. "ihdebgbhejebgehebda"
   
4. "fddhieigcggecjcjefga"
   
5. "eeabdhhchghj"
   
6. "hedeeggihjcddghhb"
   
7. "hjdihahibjbi"
   
8. ...

复制代码

输入字符串很长意味着Trie内的节点重复利用率低，也就是说输入总共有多少个字符，那么Trie里就会创建大致那个数量级的Node。

而创建一个Node的overhead很大：Python需要为Node分配内存（一个dict），然后分配内存并初始化另一个dict结构children以及一个array结构palinidx —— 这个“常数因子”太大了。假设别人100ms可以跑完，而你的程序虽然是O(n)，但均摊下来的单位操作要慢上100倍，那就是10s，也就超时了。

要想不超时的话，可能压缩Trie可以做到，或者就放弃Trie的做法吧。

时间复杂度是O(n*len(word)^2)吧，再加上python本身比较慢

qdbwfn 发表于 2018-2-14 23:35
时间复杂度是O(n*len(word)^2)吧，再加上python本身比较慢

那请问有神么可以改进的地方吗？

但是我以为lc已经优化过，时间都是跟同种语言比的？

magicsets 发表于 2018-2-17 07:10
我试着优化了一下，感觉Python用普通Trie应该是没有办法Accept的，因为这道题目的输入的字符串都很长。
...

太感谢您了 回复写的很详细 感激感激
这是不是意味着用hashmap这题会比Trie要好

或者我不用dict存children，就用tuple，每次找一下，是不是可以消除常数因子的影响

太谢谢了 以前我都没有考虑到开dict的影响

greynut 发表于 2018-2-17 07:39
太感谢您了 回复写的很详细 感激感激
这是不是意味着用hashmap这题会比Trie要好

是的用hashmap比较好

children用tuple或者list也会超时的，本质上是要创建的Node太多了

magicsets 发表于 2018-2-17 13:06
是的用hashmap比较好

children用tuple或者list也会超时的，本质上是要创建的Node太多了

那为什么其他语言不会超时呢？

是因为python什么特性吗

那我万一面试要实现trie怎么办呢？

greynut 发表于 2018-2-17 13:10
那为什么其他语言不会超时呢？

是因为python什么特性吗

其他语言也不一定不超时吧，也有可能正好卡在时间线上，比如python要5秒跑完，Java要1秒，而LeetCode卡2秒，那python的就TLE了。

面试要实现trie要么不会出这道题目，要么不会测试同样量级的数据，要么不会卡同样短的时间。

换言之，这道题你是正确地用python实现了trie，但题目本身的测试数据并不是为测试你用trie解决该问题的能力而设计的。

magicsets 发表于 2018-2-17 13:22
其他语言也不一定不超时吧，也有可能正好卡在时间线上，比如python要5秒跑完，Java要1秒，而LeetCode卡2 ...

之前有遇一題，我試試用人家的答案跑一下看看有多快，cod基本上跟我的一樣。。。我precompute一個sum（兩個int加起來而己啊！），在for loop裡取用，媽的，給我TLE。不precompute卻跑完所有test cases。
從此我對leetcode有一種既愛既恨的感覺。。。