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