Playing with tries and errors

We just launched this new "spell as you type" product for Bing in Int'l markets. Question: how would you implement the below data structure and what would be your search strategy?