Given two strings, S1 and S2, we can define an edit distance as the minimum number of operations required to change S1 to S2.
The operations might be one of the following:
- delete a character
- insert a character
- substitute a character for another character