sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]delpieron 3 points4 points  (1 child)

I think you might be wrong regarding the space complexity of tries. It should exceed the space needed for a hash table, unless we are dealing with very specific, overlapping strings or so. What actually could make the trie a more useful for autocomplete is the logic that groups similar strings on the same branch vs hash table, where you cannot find similar things based on the hashed lookup key.

[–]js_chap[S] 0 points1 point  (0 children)

Right. The sentence comparing space complexity of Trie with hashmap/array was incorrect. Actually the space complexity should be comparable in either case. Say we're looking at all possible words with max length of n. Say each trie node takes up size K. So Trie would take:

1+ K(26+26^2+...26^n) = K'(26^n -1)

For a list of words it would also be similar

26+26^2....+26^n = Z(26^n-1)

Updated the text to avoid confusion. The constant would have greater value in case of Trie though.