This problem was asked by Google.
The edit distance between two strings refers to the minimum number of character
substitutions required to change one string to the other. For example, the edit distance between
three: substitute the
s, substitute the
i, and append a
Given two strings, compute the edit distance between them.