I posted this in the C# forum, even though it's more algorithmic in nature, since I thought that C# might have something that could make the task a bit easier.
Basically, I want to code something like the mobile phone dictionaries. The words that the current combination of characters could make up is are displayed, and change every time you type - I'm sure you all know how it works.
I've actually implemented it successfully, but I'm just using an ArrayList, and with, well, a couple of hundred kilobytes of words, an O(n) search is a bit slow. Dictionary would be preferable, or some kind of hashtable, but since I'm looking for parts of words, I can't really use that.
So, I'm wondering - what do you think would be an optimal algorithm for such a dictionary? I was thinking that I could implement a BST combined with linked lists, but that'd use insane amounts of memory as far as I can see.
Any ideas?
