Edit Distance Problem: Dynamic Programming Deep Dive with Java

Every time you mistype a word and your IDE quietly corrects it, or you run git diff and see which lines changed, or a bioinformatics pipeline aligns two DNA strands — the edit distance algorithm is likely doing the heavy lifting. It's one of those rare algorithms that quietly powers a dozen industries simultaneously. Knowing it deeply, not just being able to recite the recurrence relation, is what separates candidates who get offers from those who don't.

The edit distance problem (formally called Levenshtein distance) asks: given two strings, what is the minimum number of single-character operations — insert, delete, or substitute — required to transform one string into the other? The naive recursive solution recomputes the same subproblems exponentially. Dynamic programming collapses that exponential tree into an O(m×n) table where every cell is computed exactly once. The trick is recognising that the optimal answer for transforming any prefix of string A into any prefix of string B depends only on three smaller subproblems — and that insight is the whole game.

By the end of this article you'll be able to: build the full DP table from scratch and explain every cell intuitively, reconstruct the actual sequence of edit operations (not just the count), optimize the solution down to O(min(m,n)) space, handle Unicode and multi-byte strings correctly, and answer every interview follow-up an interviewer can throw at you. Let's build it piece by piece.

What is Edit Distance (Levenshtein Distance)? — Plain English

Edit Distance (also called Levenshtein Distance) measures how many single-character operations — insertions, deletions, or substitutions — are needed to transform one string into another. For example, transforming 'kitten' into 'sitting' requires 3 operations: substitute k->s, substitute e->i, insert g at the end.

Real-world uses: spell checkers compute edit distance to suggest corrections. DNA sequence alignment measures how genetically similar two organisms are. Git merge tools detect which lines were changed, inserted, or deleted.

How Edit Distance (Levenshtein Distance) Works — Step by Step

Define dp[i][j] = minimum edit distance between the first i characters of word1 and the first j characters of word2.

Base cases: dp[0][j] = j (transform empty string to word2[0..j-1] requires j insertions). dp[i][0] = i (transform word1[0..i-1] to empty string requires i deletions).

Recurrence: If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (characters match — no operation needed). Else: dp[i][j] = 1 + min( dp[i-1][j], # delete word1[i-1] dp[i][j-1], # insert word2[j-1] into word1 dp[i-1][j-1] # substitute word1[i-1] with word2[j-1] )

Time: O(mn). Space: O(mn) for full table, O(min(m,n)) with rolling rows.

Worked Example — Tracing the Algorithm

Transform 'horse' into 'ros'.

dp table (rows=horse, cols=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 ]

Fill example at dp[2][2] (o vs o): word1[1]='o' == word2[1]='o'. dp[2][2] = dp[1][1] = 1. Fill at dp[5][3] (e vs s): 'e' != 's'. min(dp[4][3], dp[5][2], dp[4][2]) = min(2,4,3) = 2. Add 1 = 3.

Answer: dp[5][3] = 3. Operations: delete h, delete r, substitute e->s. (or: substitute h->r, delete o, delete r... multiple valid paths)

Implementation

The following implementation demonstrates Edit Distance (Levenshtein Distance) with clear comments.

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    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 word1[i-1] == word2[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]   # substitute
                )
    return dp[m][n]

print(edit_distance('horse', 'ros'))    # 3
print(edit_distance('kitten', 'sitting')) # 3
print(edit_distance('', 'abc'))          # 3

Frequently Asked Questions