# How to Calculate Edit Distance Between Two Strings Using DP

> Learn to calculate edit distance between two strings using dynamic programming. This guide explains DP transitions and O(m*n) complexity for efficient string comparison.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**To calculate the edit distance between two strings using dynamic programming, define `dp[i][j]` as the minimum operations to transform the first `i` characters of `s1` into the first `j` characters of `s2`, fill the table using insertion, deletion, and replacement transitions, and return `dp[m][n]` for O(m·n) time complexity.**

The edit distance (Levenshtein distance) is a classic dynamic programming problem that measures the minimum number of single-character **insert**, **delete**, or **replace** operations required to transform one string into another. This article extracts the complete solution strategy from the `labuladong/fucking-algorithm` repository, specifically from `动态规划系列/编辑距离.md`, providing the three canonical Java implementations used to master this fundamental algorithm.

## Understanding the Edit Distance Problem

Edit distance quantifies the similarity between two strings, `s1` and `s2`, by counting the minimum operations needed to convert `s1` into `s2`. The permitted operations are inserting a character, deleting a character, or replacing one character with another. According to the source article in the `labuladong/fucking-algorithm` repository, solving this efficiently requires avoiding the exponential time complexity of naive recursion through dynamic programming optimization.

## DP State Definition and Recurrence Relation

The core of the solution lies in properly defining the sub-problems and their relationships.

### Defining the DP State

Let `dp[i][j]` represent the **edit distance between the prefixes** `s1[0..i-1]` and `s2[0..j-1]`. The final answer resides in `dp[m][n]`, where `m = s1.length()` and `n = s2.length()`. This state definition captures exactly how many operations are needed to align the first `i` characters of the source string with the first `j` characters of the target string.

### Base Cases

The boundary conditions handle empty prefixes straightforwardly:

- If `i == 0`, we must insert all `j` characters of `s2` into the empty string: `dp[0][j] = j`.
- If `j == 0`, we must delete all `i` characters of `s1` to reach the empty string: `dp[i][0] = i`.

### State Transition

For the general case when both prefixes are non-empty, we examine the current characters `s1[i-1]` and `s2[j-1]`:

- If the characters **match**, no operation is needed: `dp[i][j] = dp[i-1][j-1]`.
- If they differ, we consider the three possible operations and select the minimum cost plus one:

```

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
)

```

## Three Implementation Approaches from the Source Code

The repository `labuladong/fucking-algorithm` provides three implementations that progress from naive recursion to production-ready dynamic programming.

### 1. Plain Recursive Solution (Exponential)

This brute-force approach, shown in lines 21-47 of `动态规划系列/编辑距离.md`, illustrates the recurrence logic but suffers from exponential time complexity due to overlapping sub-problems.

```java
class Solution {
    public int minDistance(String s1, String s2) {
        return dp(s1, s1.length() - 1, s2, s2.length() - 1);
    }

    private int dp(String s1, int i, String s2, int j) {
        if (i == -1) return j + 1;    // insert all remaining chars of s2
        if (j == -1) return i + 1;    // delete all remaining chars of s1
        if (s1.charAt(i) == s2.charAt(j))
            return dp(s1, i - 1, s2, j - 1);   // skip equal chars
        return 1 + Math.min(
                dp(s1, i - 1, s2, j),      // delete
                Math.min(
                    dp(s1, i, s2, j - 1),  // insert
                    dp(s1, i - 1, s2, j - 1) // replace
                )
        );
    }
}

```

### 2. Memoised Top-Down (Optimized Recursion)

The "备忘录解法" (memoization) section eliminates redundant calculations by storing computed states in a 2D array. This reduces the complexity to polynomial time while maintaining the recursive structure.

```java
class Solution {
    private int[][] memo;

    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dp(s1, m - 1, s2, n - 1);
    }

    private int dp(String s1, int i, String s2, int j) {
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;
        if (memo[i][j] != -1) return memo[i][j];
        if (s1.charAt(i) == s2.charAt(j))
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        else
            memo[i][j] = 1 + Math.min(
                    dp(s1, i - 1, s2, j),
                    Math.min(dp(s1, i, s2, j - 1),
                             dp(s1, i - 1, s2, j - 1)));
        return memo[i][j];
    }
}

```

### 3. Iterative Bottom-Up DP Table (Production-Ready)

The "DP table 解法" section presents the industry-standard approach using nested loops to fill the table iteratively. This avoids recursion overhead and provides optimal cache performance.

```java
class Solution {
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        // base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;   // deletions
        for (int j = 0; j <= n; j++) dp[0][j] = j;   // insertions

        // fill table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];      // skip
                else
                    dp[i][j] = 1 + Math.min(
                            dp[i - 1][j],           // delete
                            Math.min(dp[i][j - 1],   // insert
                                     dp[i - 1][j - 1])); // replace
            }
        }
        return dp[m][n];
    }
}

```

## Complexity Analysis and Space Optimization

The **time complexity** for all optimized DP approaches is **O(m·n)**, as each cell of the `(m+1) × (n+1)` table is computed exactly once. The **space complexity** is **O(m·n)** for storing the full DP table.

As noted in the "空间复杂度压缩" (space complexity compression) paragraph of `动态规划系列/编辑距离.md`, you can reduce space to **O(min(m, n))** by maintaining only two rows (or columns) of the table, since computing the current row requires only the previous row's values.

## Summary

- **Edit distance** measures the minimum insert, delete, and replace operations between two strings.
- The **DP state** `dp[i][j]` captures the cost to transform `s1[0..i-1]` into `s2[0..j-1]`.
- **Base cases** handle empty strings by counting total insertions or deletions.
- The **recurrence** chooses the minimum cost among three operations when characters differ.
- **Implementation** progresses from exponential recursion to memoised top-down, culminating in the efficient bottom-up table approach with **O(m·n)** time complexity.

## Frequently Asked Questions

### What is the time complexity of the edit distance DP algorithm?

The standard dynamic programming solution runs in **O(m·n)** time, where `m` and `n` are the lengths of the two input strings. Each cell in the DP table is computed once using constant-time operations. The naive recursive solution without memoization runs in exponential time, which is why the DP optimization is essential.

### Can the space complexity of edit distance be optimized?

Yes, the space complexity can be reduced from **O(m·n)** to **O(min(m, n))**. Since calculating the current row of the DP table only requires the previous row, you can discard older rows and maintain just two arrays (or even one array with careful indexing). The `labuladong/fucking-algorithm` article discusses this optimization in the space compression section.

### How do I reconstruct the actual edit operations from the DP table?

To recover the specific sequence of insertions, deletions, and replacements, augment each DP cell to store the operation that yielded the optimal value. By backtracking from `dp[m][n]` to the base cases following these stored pointers, you can reconstruct the full edit path. The repository's article covers this extension in the "扩展延伸" section of `动态规划系列/编辑距离.md`.

### Why does the recursive solution use -1 as the base case index?

The recursive implementation uses 0-based indexing where `i` and `j` represent the current character positions. When `i == -1`, it signifies that all characters of `s1` have been exhausted (empty prefix), requiring `j + 1` insertions to match `s2`. Similarly, `j == -1` indicates `s2` is exhausted, requiring `i + 1` deletions. This convention aligns with the definition that converting an empty string to a string of length `k` requires exactly `k` operations.