edit distance

The minimum number of single-character insertions, deletions and substitutions needed to turn one string into another.

In more detail

Turning "kitten" into "sitting" takes three edits. Dynamic programming fills a table where each cell takes the cheapest of the three moves from its neighbours, in O(m × n). Spell checkers and fuzzy search use it to find near matches.

Examples

examp1e.com  edits: 1
example-invoices.com  edits: 9
The course computes edit scripts with Python's difflib.SequenceMatcher.

Related terms

Taught in

References