Edit Distance

Edit distance (or Levenshtein distance) is the smallest number of single-character edits that turn one string into another. Three edits are allowed, each costing 1:

• insert a character,
• delete a character,
• substitute one character for another.

Task: write edit_distance(a, b) returning that minimum number as an integer.

The standard approach fills a table where d[i][j] is the distance between the first i characters of a and the first j characters of b.

• Base cases: d[i][0] = i (delete every character) and d[0][j] = j (insert every character).
• Each other cell is the cheapest of three options:
  • d[i-1][j] + 1 — delete a[i-1],
  • d[i][j-1] + 1 — insert b[j-1],
  • d[i-1][j-1] + cost — substitute, where cost is 0 if the two characters already match and 1 if they don't.

The answer sits in the bottom-right corner.

• Either string may be empty, in which case the distance is simply the other one's length.
• Identical strings give 0.
• Comparison is case-sensitive.

The reason the table works is that every cell's answer only needs the three cells above and to its left, which are already final by the time you reach it. That's dynamic programming in one sentence — and it's why this runs in len(a) × len(b) steps instead of exploring an exponential tree of possible edit sequences.