Siriuslight's blog

Deciding size of 2D array for trie.
By Siriuslight, history, 7 years ago, In English

If I want to implement trie using two dimensional array, how should I decide the size of array.

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

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In worst case the trie will have number of nodes equal to the sum of lengths of the strings from the input, let's call that s. In worst case, each node will have number of edges equal to the size of the alphabet, let's call that a. So, it should be s × a.

→ Reply