Edit Distance

The Levenshtein distance between two strings is the minimum number of single-character insertions, deletions, or substitutions to transform one into the other.

"kitten" -> "sitting"  distance 3:
  kitten -> sitten    (substitute k -> s)
         -> sittin    (substitute e -> i)
         -> sitting   (insert g)

Standard dynamic programming:

Time: O(NM). Space: O(NM) but can be reduced to O(min(N,M)).

For diff specifically: we usually count line-level edits, not character-level. Diff is "shortest edit script" between sequences of lines.