Find the minimum edit distance between two strings Explanation

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 AB and A is 1, because deletions cost 1 and the only edit needed is the deletion of the B character.

The distance between CAR and FAR is 2, because substitutions cost 2. Another way to look at this is one deletion and one insertion.

Rules

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
&gt; 1
MART, KARMA
&gt; 5
KITTEN, SITTING
&gt; 5
INTENTION, EXECUTION
&gt; 8
brainfuck, 2680

+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;++++++&gt;,&lt;[-&gt;-----&lt;]&gt;--[+++++++++++++++++++++
+++++++++++&gt;&gt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;+&lt;&lt;,--------------------------------]&gt;&gt;[-&lt;&lt;&lt;
+&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;]&gt;[-&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;]&gt;[&gt;&gt;],----------[++++++++++&gt;&gt;
[-&gt;&gt;+&lt;&lt;]&gt;&gt;+&lt;&lt;,----------]&gt;&gt;[-&lt;&lt;&lt;+&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;]&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;[
-&lt;+&gt;&gt;+&lt;]&lt;&lt;&lt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;+&lt;&lt;&lt;]&gt;&gt;&gt;[-&lt;+&gt;]&lt;[-&gt;+&gt;+&lt;&lt;]&lt;[-&lt;+&gt;]&lt;[-&gt;+&gt;+&lt;&lt;]
&lt;[-&lt;+&gt;&gt;+&lt;]&lt;[-&gt;+&lt;]&gt;&gt;&gt;&gt;&gt;&gt;[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;[-&gt;&gt;+
&gt;+&lt;&lt;&lt;]&gt;&gt;&gt;[-&lt;&lt;&lt;+&gt;&gt;&gt;]&lt;[-&gt;&gt;+[-&gt;+&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;&gt;[-]&lt;[&lt;&lt;]&lt;&lt;&lt;+[-&gt;&gt;&gt;+
&lt;&lt;&lt;]&gt;&gt;&gt;[-&lt;+&lt;&lt;+&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;[-&gt;&gt;[-&gt;&gt;&gt;&gt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;
+&lt;&lt;]&gt;&gt;&gt;&gt;]&gt;&gt;[-&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;[-&lt;&lt;&lt;&lt;+&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;+[-&gt;&gt;+&lt;&lt;]&gt;&gt;[-&lt;&lt;+&lt;+&gt;&gt;&gt;
]&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;[-]&gt;&gt;[-]&gt;&gt;[-]-[+&lt;&lt;-]+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;+&gt;]&lt;[-&gt;+&lt;&lt;&lt;&lt;+&gt;
&gt;&gt;]&lt;&lt;&lt;[-&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;+&gt;]&lt;[-&gt;+&lt;&lt;&lt;&lt;+&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;&lt;[-]&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;
&gt;&gt;&gt;[-&lt;+&gt;]&lt;[-&gt;+&gt;+&lt;&lt;]&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;[-&gt;+&lt;]&gt;[-&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;]&lt;&lt;&lt;[-&gt;+&lt;]
&gt;[-&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;[-&gt;&gt;+&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;]
&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;-
[-&lt;&lt;[-&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[-&gt;&gt;+&gt;&gt;+&lt;&lt;&lt;&lt;]&gt;&gt;[-&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;
+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;&gt;&gt;&gt;]&gt;&gt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;[-&lt;&lt;+&gt;&gt;&gt;&gt;+&lt;&lt;]-&gt;&gt;-[-[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;[-
&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;+&lt;&lt;]&lt;&lt;&lt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;+&lt;&lt;]+[-&gt;&gt;[-&lt;&lt;+&gt;&gt;]&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;+
]&lt;&lt;&lt;&lt;&lt;&lt;[-&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[-&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;]
-&lt;&lt;[-]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[-&gt;&gt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;&gt;-[
-[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&lt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;+&lt;&lt;]+[-&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;+]&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;&lt;
&lt;-[+&gt;&gt;[-&lt;&lt;+&gt;&gt;]&gt;&gt;[-&lt;&lt;+&gt;&gt;]&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]+&gt;&gt;&gt;[-]&lt;[-&gt;+&lt;]&gt;&gt;&gt;[-]&lt;[-
&gt;+&lt;]&gt;&gt;&gt;[-]&lt;[-&gt;+&lt;]&gt;&gt;&gt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;
&gt;&gt;&gt;-[-[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;[-&gt;+&lt;]&gt;[-&lt;+&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;-[+&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;-]+&gt;&gt;[-&lt;+&gt;]&gt;
&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;
&lt;]&gt;&gt;&gt;&gt;-[-[-&gt;&gt;+&lt;&lt;]&gt;&gt;]&gt;[-&gt;+&lt;]&gt;[-&lt;+&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;-[+&gt;&gt;[-&lt;&lt;+&gt;&gt;]&lt;&lt;&lt;&lt;-]+&gt;[-&gt;-&lt;
]&gt;[-&lt;[-]+&gt;]&lt;[-&gt;&gt;&gt;+&lt;&lt;&lt;]&gt;&gt;&gt;[-&lt;&lt;+&lt;+&gt;&gt;&gt;]&lt;&lt;-[+&gt;[-&gt;+&lt;]&lt;]&lt;[-&gt;&gt;+&lt;-[[-]&gt;[-&gt;+
&lt;]&gt;[-&lt;+&gt;&gt;&gt;+&lt;&lt;]+&gt;&gt;[-&lt;&lt;[-]&gt;&gt;]&lt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;+&lt;&lt;]+&gt;&gt;[-&lt;&lt;[-]&gt;&gt;]&lt;[-&gt;+&lt;]&gt;
[-&lt;+&gt;&gt;&gt;+&lt;&lt;]+&gt;&gt;[-&lt;&lt;[-]&gt;&gt;]&lt;&lt;[-&lt;&lt;[-]+&gt;&gt;]&lt;&lt;[-&lt;&lt;[-]+&gt;&gt;]&lt;&lt;[-&lt;&lt;[-]+&gt;&gt;]&lt;&lt;&lt;+
&gt;-&gt;-&gt;&gt;-&gt;&gt;-&lt;&lt;&lt;&lt;&lt;]&lt;[-&gt;+&lt;]]&gt;[-&lt;+&gt;]&gt;&gt;[-&lt;&lt;&lt;+&gt;&gt;&gt;]&lt;&lt;&lt;[-&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;
&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;[-&gt;+&lt;]&gt;[-&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;
&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;&gt;&gt;+&lt;&lt;&lt;]&gt;&gt;&gt;[-&lt;&lt;+&lt;+&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;[-&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;
&gt;[-&lt;&lt;&lt;&lt;&lt;+&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]
&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[-&lt;&lt;[-&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;[-&gt;&gt;+&gt;
&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;[-&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;
+&lt;&lt;]&gt;&gt;]&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;[-]&lt;&lt;[-&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;]&lt;&lt;[
-&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;]-[+&lt;&lt;-]+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[-&gt;+&lt;]&lt;&lt;[-&gt;+&lt;]&lt;&lt;[-&gt;
+&lt;]&gt;&gt;&gt;&gt;&gt;[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;[-&gt;&gt;[-&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;]&gt;&gt;
&gt;&gt;[-&lt;&lt;+&lt;&lt;+&gt;&gt;&gt;&gt;]&lt;&lt;+[-[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;]&lt;&lt;&lt;&lt;]&gt;&gt;[-[-&gt;
&gt;+&lt;&lt;]&gt;&gt;]&gt;&gt;&gt;&gt;++++++++++&lt;[-&gt;-[&gt;+&gt;&gt;]&gt;[+[-&lt;+&gt;]&gt;+&gt;&gt;]&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;[-&gt;-[&gt;+&gt;&gt;]&gt;
[+[-&lt;+&gt;]&gt;+&gt;&gt;]&lt;&lt;&lt;&lt;&lt;]&gt;[-]&lt;++++++[-&gt;++++++++[-&gt;+&gt;+&lt;&lt;&lt;&lt;+&gt;&gt;]&lt;]&gt;&gt;&gt;.&lt;.&lt;&lt;&lt;.


Using dynamic programming, of course.

Input strings should be separated by a space, and followed by a new line. For example:

INTENTION EXECUTION
008