In order to make autocorrect suggestions, a program needs to be able to tell how close two words are to each other. The edit distance between two words is the number of changes that you would need to make to convert one word into the other. For example, to convert dungeons into dragons, you could use the following steps:
- Remove u to get dngeons
- Insert r to get drngeons
- Remove the first n to get drgeons
- Remove e to get drgons
- Insert a to get dragons
This route gives an edit distance of five because it uses five steps, but for some words it may not be obvious that you have found the shortest path between the two words.
For this problem, write a program similar to the one shown in the following screenshot, which finds the edit distance between two words:
If you don't know how to get started, the first part of the solution describes an approach that you can take.