vendredi 27 mars 2015

Fetch Words Starting/Containing/Ending With Fragment in a Word Dictionary


Assuming that we have a list of all dictionary words from A-Z from the English dictionary.


I have three cases to perform on these list of words:


1) find out all the words that are "starting with" a particular fragment



eg: If my fragment is 'car', word 'card' should be returned


2) find out all the words that "contains" the fragment as the substring



eg: If my fragment is 'ace', word 'facebook' should be returned


3) find out all the words that are "ending with" a particular fragment



eg: If my fragment is 'age', word 'image' should be returned


After some searching exercise on the internet, I found that 1) can be done through trie/compressed trie and 3) can be done through suffix tree.


I am unsure of how 2) can be achieved. Plus are there any better scenarios wherein all these three cases can be handled? As maintaining both prefix and suffix tree could be a memory intensive task.


Kindly let me know for any other areas to look out for.


Thanks in advance.


PS: I will be using C++ to achieve this




Aucun commentaire:

Enregistrer un commentaire