Compute the Edit Distance Between Two Strings solved by 809

In 1966, Vladimir Levenshtein introduced the notion of the edit distance between two strings as the minimum number of edit operations needed to transform one string into another. Here, an edit operation is the insertion, deletion, or substitution of a single symbol. For example, TGCATAT can be transformed into ATCCGAT with five edit operations, implying that the edit distance between these strings is at most 5.

Edit Distance Problem

Find the edit distance between two strings.

Given: Two amino acid strings.

Return: The edit distance between these strings.

Sample Dataset

PLEASANTLY
MEANLY

Sample Output

5

Extra Dataset

Click for an extra dataset