Edit Distance (Levenshtein): DP Solution Explained

Edit Distance (Levenshtein Distance) is a classic string DP problem that appears in interviews at Google, Microsoft, and Dropbox. It’s the algorithm behind spell checkers, diff tools, DNA sequence alignment, and fuzzy search. Understanding it demonstrates mastery of 2D DP with multiple operation types.

Problem

Given two strings, find the minimum number of operations (insert, delete, replace) to transform one string into the other.

s1 = "horse", s2 = "ros"
Operations: horse → rorse (replace h→r) → rose (delete r) → ros (delete e)
Edit distance: 3

DP Solution

def edit_distance(s1: str, s2: str) -> int:
    """
    dp[i][j] = min operations to convert s1[:i] to s2[:j].
    Base cases:
        dp[0][j] = j (j insertions to build s2 from empty string)
        dp[i][0] = i (i deletions to reduce s1 to empty string)
    Transition:
        If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]  (no operation needed)
        Else: dp[i][j] = 1 + min(
            dp[i-1][j],    # Delete from s1
            dp[i][j-1],    # Insert into s1
            dp[i-1][j-1]   # Replace in s1
        )
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i  # Delete all characters of s1[:i]
    for j in range(n + 1):
        dp[0][j] = j  # Insert all characters of s2[:j]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # Characters match, no op needed
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],     # Delete s1[i-1]
                    dp[i][j - 1],     # Insert s2[j-1] into s1
                    dp[i - 1][j - 1]  # Replace s1[i-1] with s2[j-1]
                )

    return dp[m][n]

print(edit_distance("horse", "ros"))     # 3
print(edit_distance("intention", "execution"))  # 5

Space-Optimized Version

def edit_distance_optimized(s1: str, s2: str) -> int:
    """Space-optimized: O(min(m, n))."""
    if len(s1) < len(s2):
        s1, s2 = s2, s1  # Ensure s2 is shorter

    m, n = len(s1), len(s2)
    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr

    return prev[n]

Interpreting the DP Table

The DP table for “horse” → “ros”:

    ""  r   o   s
""  [0, 1,  2,  3]
h   [1, 1,  2,  3]
o   [2, 2,  1,  2]
r   [3, 2,  2,  2]
s   [4, 3,  3,  2]
e   [5, 4,  4,  3]  ← dp[5][3] = 3

Reconstructing the Operations

def edit_distance_with_ops(s1: str, s2: str):
    """Return edit distance and the list of operations."""
    m, n = len(s1), len(s2)
    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 s1[i-1] == s2[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])

    # Backtrack to find operations
    ops = []
    i, j = m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i-1] == s2[j-1]:
            i -= 1; j -= 1  # Match, no operation
        elif j > 0 and (i == 0 or dp[i][j-1] <= dp[i-1][j] and dp[i][j-1]  0 and (j == 0 or dp[i-1][j] <= dp[i][j-1] and dp[i-1][j] <= dp[i-1][j-1]):
            ops.append(f"Delete '{s1[i-1]}' at position {i-1}")
            i -= 1
        else:
            ops.append(f"Replace '{s1[i-1]}' with '{s2[j-1]}' at position {i-1}")
            i -= 1; j -= 1

    return dp[m][n], list(reversed(ops))

Applications

Spell checking: Suggest words with edit distance 1-2 from the misspelled word
DNA sequence alignment: With weights: match=+1, mismatch=-1, gap=-2 (Smith-Waterman algorithm)
Fuzzy search: Elasticsearch uses edit distance for “did you mean?” suggestions
Diff tools: git diff reduces to finding the LCS, which minimizes edits (Myers diff algorithm)

Practice Problems

LeetCode 72: Edit Distance
LeetCode 583: Delete Operation for Two Strings (only insert/delete)
LeetCode 712: Minimum ASCII Delete Sum for Two Strings (weighted deletes)
LeetCode 161: One Edit Distance (just check if exactly 1 edit apart)