Edit Distance Theory

Classical dynamic programming formulation for measuring similarity between strings.

State

dp[i][j] distance

Base

dp[i][0]=i dp[0][j]=j

Transitions

match/insert/delete/replace

1. Recurrence

if a[i-1] == b[j-1]:
  dp[i][j] = dp[i-1][j-1]
else:
  dp[i][j] = 1 + min(dp[i-1][j],   # delete
                      dp[i][j-1],   # insert
                      dp[i-1][j-1]) # replace

2. Space Optimization

Only previous row needed → O(min(m,n)) by iterating over shorter string horizontally.

3. Variants

Damerau-Levenshtein: allow adjacent transposition (check i>1,j>1,a[i-1]==b[j-2],a[i-2]==b[j-1]).
Weighted operations: assign cost to insert/delete/replace.
Similarity ratios: 1 - distance / max(m,n).

← Simulation Next: Matrix Chain →