DSA

Edit Distance

Covers: Recursive, DP. Optimal — Time O(m*n), Space O(n).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePractice

Practice Link

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Recursive#

At each step we compare the last characters of the two current prefixes. If they match, no edit is needed and we recurse on (m-1, n-1). If they differ, we try all three edits — insert (advance n), delete (advance m), replace (advance both) — each costing 1, and take the minimum. Base cases: converting a non-empty string to empty costs m deletes and vice versa. Without caching, the branching factor of 3 gives O(3^n) time.

cpp
class Solution {
public:
    int eD(string s1, string s2, int m, int n)
    {
        if(m==0)
            return n;
        if(n==0)
            return m;
        if(s1[m-1] == s2[n-1])
            return eD(s1, s2, m-1, n-1);
        else 
            return 1 + min(eD(s1, s2, m, n-1), min(eD(s1, s2, m-1, n), eD(s1, s2, m-1, n-1)));
    }
    
    int minDistance(string word1, string word2) {
        return eD(word1, word2, word1.length(), word2.length());
    }
};

O(3^n) -> TLE (Overlapping subproblems)

DP Approach#

Build a 2D table where dp[i][j] = minimum edits to convert word1[0..i-1] to word2[0..j-1]. Initialize the first row/column with deletion costs (dp[i][0] = i, dp[0][j] = j). Fill each cell by reusing the three smaller sub-problems (left = insert, top = delete, diagonal = replace/match). The answer is at dp[m][n], computed in O(m*n) time and space with no recursion overhead.

cpp
class Solution {
public:
    int eD2(string s1, string s2, int m, int n)
    {
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        
        for(int i=0;i<=m;i++)
            dp[i][0] = i;
        
        for(int j=0;j<=n;j++)
            dp[0][j] = j;
        
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                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], min(dp[i-1][j-1], dp[i][j-1]));
            }
        }
        return dp[m][n];
    }
    
    int minDistance(string word1, string word2) {
        return eD2(word1, word2, word1.length(), word2.length());
    }
};

Time Complexity: O(m*n)

Space Compelexity: O(m*n)

Space Optimized Tabulation#

dp[i][j] only reads from dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] — the previous row and the current row's previous column. We replace the full 2D table with two 1D arrays (prev and curr), swapping after each row. Space falls from O(mn) to O(n) while time remains O(mn).

cpp
class Solution {
public:

    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> prev(n+1, 0);
        vector<int> curr(n+1, 0);

        for(int j=0;j<=n;j++)
            prev[j] = j;
        
        for(int i=1;i<=m;i++)
        {
            curr[0] = i;
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1] == word2[j-1])
                    curr[j] = prev[j-1];
                else
                    curr[j] = 1 + min(curr[j-1], min(prev[j-1], prev[j]));
            }
            prev = curr;
        }

        return prev[n];
    }
};

Time Complexity: O(m*n)

Space Compelexity: O(n)

Related articles

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).