AMR-KELEG's blog

Trie Implementation help
By AMR-KELEG, history, 9 years ago, In English

I would like to know if implementing the trie using a Node struct(class) is considered a good way of implementing it in competitive programming.

I saw that some programmers use a multidimensional array to implement it which seems a bit confusing.

Thanks

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Dynamic allocation is considered to be a little bit slower than the static one since it consumes time while the program is running while the static allocation does that during the compilation time, although I believe that if your algorithm is well designed it won't be an advantage to use static arrays over allocation during the run time .

Ignore the code I wrote, I just messed up xD

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

There are a lot of ways, how to implement Trie. My favourite implementations using map, and using linked list.

  1. std::map: http://pastebin.com/fyqsH65k
  2. linked list: http://pastebin.com/kUYHiLRC

These implementations use O(s1 + s2 + ... + sn) memory.

→ Reply