Блог пользователя AMR-KELEG

Trie Implementation help
Автор AMR-KELEG, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить