I have a list of english words. I'm trying to come up with a data structure that allows me to do fast StartsWith filtering, like:
var words = dictionary.StartsWith("foo");
I was thinking of creating a data structure like this:
But I wanted to ask first:
a) Does the above data structure already have a name?
b) Is this the fastest way to implement what I'm looking for?
Edit: The data structure will be built at the beginning and not change. I'll only need to do the equivalent of StartsWith and Contains.
Best Answer
Check ternary search tries: http://en.wikipedia.org/wiki/Ternary_search_tree
It has very effective (probably the most effective) algorithm for word lookups including partial match.
If this is close to auto-complete implementation case then check this: http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/