CODEWITHSUNDEEP
data-structurestrie
techcraver
techcraver

Reputation: 411

what are some other possible use cases of a Trie data structure other than T9/Spell checker dictionaries?

I am trying to understand Trie data structure & I've understood that they are used in Spell checkers/Auto suggest or correct spellings etc. i.e. especially used in the context of language dictionaries. I wonder if there are any other possible use cases for a Trie data structure (as it is or in any augmented form).

Thanks for advance.

PS: This is not a homework problem & I am here trying to better understand possible usecases for a Trie data structure and that's it.

Upvotes: 1

Views: 2214

Answers (1)

Programmer Person
Programmer Person

Reputation: 618

Tries are integral in routing systems.

Most routers stores IP address in a form of a trie (Patricia Trees) which are well suited for lookups etc.

Tries are useful as a lookup structure where you are dealing with strings (of bytes/bits etc).

Suffix trees are essentially tries and have wide string related applications, like substring checks, finding repeated substrings, palindrome finding etc.

Here are a couple of algorithm puzzles for you to try out.

  • Given an nxn binary matrix (of zeroes and ones), eliminate the duplicate rows.

  • Given n numbers, find two numbers x,y among those such that x XOR y (the exclusive OR) is maximum among all the n^2 possibilities.

Upvotes: 3

Related Questions