Search code examples
algorithmspell-checkinglevenshtein-distance

Detect matching patterns between strings

I'm making an application for learning to spell certain words. Currently my task is to detect the matching letters between the user input and the correct word (highlight the user where the error was). For example:

enter image description here

How can I do this? Is there some kind of known algorithm for this?

Thanks

Solution

  • There is a lot of research that has been already done on the problem that you have encountered - Spelling Correctors. It is most popularly used by search engines to correct user queries.

    However, the subset of the problem that you are trying to solve can be solved by using Levenshtein distance. You need to modify the original implementation to figure out the edits and mark them as red.

    This particular article by Peter Norvig clearly stands out. The article also contains links for a quick implementation in lots of programming languages. It has the right balance of the math and concepts along with code.