LashaBukhnikashvili's blog

By LashaBukhnikashvili, history, 6 years ago, In English

I'm trying to solve this problem and I am using Trie.my code.

Here maximum number nodes of Trie is less than 25*1000000,But for each node I have array of 26 elements,and memory is growing up to 25*25*1000000 in worst case.I saw other codes and they are using 2 links,can't understand it,if you can,help me to understand idea of such Trie with compressed array.

P.S to use vector for each node, instead of array, then I will lost time for Build Trie(for finding some character of some node) and there should be *26 TL,and I don't want this

solved my oversight :)

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

u missed that string can contain only a and b character ,thus 2 link