Levenshtein Distance

Type two strings and read off the fewest edits that turn one into the other, with the table it came from. Diff Checker does the same thing line by line.

Source string

Target string

Edit distance

The DP table

Each cell holds the fewest edits needed to turn that many characters of the source into that many characters of the target. Highlighted cells are the cheapest path back from the bottom-right corner. Ties are broken in a fixed order, diagonal then up then left, so the same two strings always give the same path.

The edit sequence

Nothing to transform yet.