The edit distance between two strings is a function of the minimum possible number of insertions, deletions, or substitutions to convert one word into another word.
Insertions and deletions cost 1, and substitutions cost 2.
For example, the distance between
A is 1, because deletions cost 1 and the only edit needed is the deletion of the
The distance between
FAR is 2, because substitutions cost 2. Another way to look at this is one deletion and one insertion.
Given two input strings (supplied however is convenient in your language), your program must find the minimum edit distance between the two strings.
You may assume that the strings only contain the characters
A-Z and have fewer than 100 characters and more than 0 characters.
This is code golf, so the shortest solution wins.
Sample Test Cases
ISLANDER, SLANDER > 1 MART, KARMA > 5 KITTEN, SITTING > 5 INTENTION, EXECUTION > 8