Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

derAdler's blog

Why use Trie at all??
By derAdler, history, 8 years ago, In English

hello guys, i know this might sound silly. I was just studying trie the other day and i wanted to ask that why do we use it at all we can maintain a directed graph of 26*26 where G[i][j] corresponds to whether j is a child of letter i. Could somebody explain how i am wrong with an example. Any help would be appreciated. Thanks a lot in advance.

  • Vote: I like it
  • -24
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How would you represent the following input strings in your trie?

1- ham 2- ed 3- me

a trie should support looking up a word in linear time, would you report found or not found for the string "hamed" ??

→ Reply
»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Consider aba, how would you store it? The directed graph would contain a cycle which you cannot determine the length of the string.

Then you could say "let's store a number 3 at a so that we know there is a string of length 3". But then this won't work: abaca (no other strings) since you cannot distinguish ababa, abaca, acaba and acaca (all are length 5).

→ Reply