Possible Duplicate:
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”.

File: http://fileshackweb.appspot.com/download/196001/

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’)

  • 1
    \$\begingroup\$ A simple brute force doesn't seem like much of a code-challenge to me -- What about a code golf, on any string? Or make some sort of performance requirement? \$\endgroup\$ – daniero Aug 9 '12 at 12:48
  • \$\begingroup\$ Link to download does not work. \$\endgroup\$ – DavidC Aug 24 '12 at 20:58

Browse other questions tagged or ask your own question.