data structure for probable string matches

Question

what is the best data structure for the following operation :
the data structure stores a list of words
input : a string say we name it 'pre'
output : a list of all strings that have the pre as their prefix(from the list of stored words) and the words in the list should be ordered in decreasing order of their priority.
priority of a particular string is increased if it is used out of the list of strings returned as output.
i will be using this for word prediction so every time the user selects a certain word(from the list of returned words) it's priority is increased by 1.
I have already implemented a trie but it gives the output(list) in alphabetical order i want it sorted by priority.

Answer 1

The best data structure for your problem would be a trie A trie would allow for fast lookups at the expense of space.

Follow this link for more information: link