Spell Checker
A spell checker isn't anything special, but I always wanted to implement an efficient one since I was little. And I probably tried too - doing some kind of binary search to find out the approximate location of where the word would be, and then some linear search around the area and find the closest one.
Of course, doing a binary search was by no means the correct solution. For example, it would require that the first few letters at least be the same as the correct word.
Ever since I took the advanced algorithm class, I know it's possible to get pass the restriction using a dynamic programming approach. The correct word and the word typed in do not have to share the same first few letters in order to be corrected. For example, "apell" will be corrected to "spell" because that's the closest word. Effectively, the word typed in is matched against every single word in the dictionary and find the closest one. The art is to have the algorithm does so in an efficient manner by doing various search pruning and optimization.
How to use the program
After you run the program, you can start having some fun with this stand-alone spell checker. As you type in the input textbox, the closest word to what you've typed will be displayed in the "suggestion" drop down menu below. The maximum difference box allows you to specify how the spell checking would work. The greater the allowable maximum difference, the slower it would take.
Conclusion
Pretty nice eh? Drop me a line and tell me what you think about it.
