How to Calculate Edit Distance Between Two Strings Using DP

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.

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.

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.

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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}