Edit Distance (Levenshtein)

1. One-Liner

Edit distance is the minimum number of insert, delete, and substitute operations to turn string A into B, computed by dp[i][j] over prefixes.

2. The Problem It Solves

Spell checkers, DNA alignment, fuzzy search, and diff tools need a quantitative similarity metric—how costly is it to morph one sequence into another with atomic edits.

3. The Core Idea

Align prefixes: if last characters match, no extra cost; else pay 1 for the cheapest of delete from A, insert into A, or replace—each option reduces to a smaller subproblem.

4. How It Works (Step-by-Step)

Step	What Happens
1	`dp[i][0]=i`, `dp[0][j]=j`
2	If `A[i-1]==B[j-1]`: `dp[i][j]=dp[i-1][j-1]`
3	Else `1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`
4	Answer `dp[n][m]`

5. Dry Run Example

"horse" → "ros": delete, replace, delete… minimum 3 edits (one optimal path among several).

6. Key Properties

Property	Value
Metric	Non-negative integer distance
Variants	Only insert/delete (LCS gap cost), weighted costs

7. Where It Is Used

Domain	Use
NLP	Autocorrect ranking
Bioinformatics	Approximate matching

8. Interview Tips

Trace backpointer path, discuss weighted edits, O(min(n,m)) space with two rows.

9. Comparison with Other Algorithms

Problem	Cost model
Levenshtein	Insert/delete/sub
LCS	Often tied via `n+m-2·	LCS	` for equal length ops

10. Complexity

Metric	Value
Time	O(`nm`)
Space	O(`nm`) or O(`min(n,m)`)

Implementation Example (PYTHON)

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