Find the minimum edit distance between two strings
The file below (see link) contains 58,111 lines with a single lower case word on each line. Find the number of strings from this file that have a Levenshtein distance of 3 or less to the string “together”.
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. The edit distance cost for each insertion, deletion and substitution is 1.
For example, the edit distance cost between toaster and together is 3 since the following 3 edits change one into the other:
1.toaster -> togster (substitution of ‘g’ for ‘a’)
2.togster -> togeter (substitution of ‘e’ for ‘s’)
3.togeter -> together (insertion of ‘h’)