Edit Distance

Edit distance counts the fewest single-character insertions, deletions, and substitutions needed to turn one string into another.

Measuring string difference

The edit distance, or Levenshtein distance, between two strings is the minimum number of single-character edits that transform one into the other. The allowed operations are inserting a character, deleting a character, and substituting one character for another. A distance of zero means the strings are identical; larger distances mean greater difference.

The recurrence

Let D[i][j] be the edit distance between the first i characters of one string and the first j of the other. If the current characters match, D[i][j] = D[i-1][j-1] with no cost. Otherwise it is one plus the minimum of D[i-1][j] for a deletion, D[i][j-1] for an insertion, and D[i-1][j-1] for a substitution. The base cases turn an empty prefix into the other by pure insertions or deletions.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            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], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

• Time: O(m*n)
• Space: O(m*n), reducible to O(min(m,n)) for the distance alone
• Operations: insert, delete, substitute
• A variant adds transposition of adjacent characters (Damerau-Levenshtein)

Weighted and banded variants

Real applications often weight the operations differently: a substitution between similar characters may cost less than between dissimilar ones, which is how biological scoring matrices work. When the two strings are known to be similar, a banded version computes only the cells near the diagonal, cutting the cost to O(n*k) for a band of width k rather than the full O(n^2).

Where it is used

Edit distance powers spell checkers that suggest the nearest dictionary word, fuzzy search, plagiarism and duplicate detection, and DNA sequence comparison. It is a close relative of the longest common subsequence problem; both are canonical two-dimensional dynamic-programming tables that differ only in the operations they permit.