DP 33. Edit Distance | Recursive to 1D Array Optimized Solution

Transforming one string into another using minimal operations is a cornerstone string-matching problem in dynamic programming. This chapter explores the Edit Distance algorithm (LeetCode Hard), evolving step-by-step from a brute-force recursive strategy to an optimized space-efficient solution using two 1D arrays.

1. Why Do We Need Edit Distance? (Problem Statement & Status Quo)

String transformation problems frequently appear in spell checkers, DNA sequencing, auto-correct systems, and natural language processing.

Given two strings, s1 and s2, we are permitted three atomic operations on string s1:

1. Insert: Add any character anywhere in string s1.
2. Remove (Delete): Delete any character from string s1.
3. Replace: Swap any character in string s1 with a specified character.

Objective: Find the absolute minimum number of operations required to convert string s1 into string s2.

Upper Bound Guarantee

Is a conversion always possible? Yes. At worst, we can delete all characters of s1 (resulting in an empty string) and subsequently insert all characters of s2.

• Maximum steps required: $N + M$ (where $N$ is the length of s1 and $M$ is the length of s2).

2. Core Mental Model & Real-World Examples

Example 1: s1 = "horse", s2 = "ros"

• Operation 1: Replace 'h' with 'r' -> "rorse"
• Operation 2: Remove 'r' -> "rose"
• Operation 3: Remove 'e' -> "ros" (matches s2)
• Total Operations: 3 (1 replacement, 2 deletions).

Example 2: s1 = "intention", s2 = "execution"

• Total Operations: 5 minimum operations required (mix of deletions, insertions, and replacements).

Real-Life Analogy: The Editor's Markup Workflow

Imagine editing a typed manuscript (s1) to match an editor's target proof (s2). Moving character by character from left to right, you look at your current token. If it matches, you leave it alone. If it doesn't match, you evaluate three distinct costs: buying a sticky note with the correct character (Insert), crossing out the bad character (Delete), or writing over it (Replace). You always pick the path that incurs the minimum total edits.

3. The Exhaustive Recursive Approach

When tasked with finding a global minimum across branching choices ("try all possible ways"), recursion provides the natural starting framework.

Defining State Parameters

We track two pointers, i and j, traversing strings s1 and s2 respectively:

• f(i, j) signifies: Find the minimum operations to convert substring s1[0...i] into substring s2[0...j].

Recurrence Logic (Match vs. Mismatch)

1. Characters Match (s1[i] == s2[j]):

   • No operation is required. We simply shrink both pointers.
   • Cost: 0 + f(i - 1, j - 1)

2. Characters Mismatch (s1[i] != s2[j]):

   • We must take the minimum cost across all three operations, adding 1 for the current step:
     • Insert: Hypothetically insert s2[j] ahead of i. s1 pointer i stays put, while s2 pointer j shrinks. -> 1 + f(i, j - 1)
     • Delete: Delete character s1[i]. s1 pointer i shrinks, while s2 pointer j stays put. -> 1 + f(i - 1, j)
     • Replace: Replace s1[i] with s2[j]. Both pointers shrink. -> 1 + f(i - 1, j - 1)

4. Establishing Base Cases

Base cases represent the condition where one of the strings is completely exhausted (-1 index state):

• String s1 is exhausted (i < 0):
  • We have no characters left in s1, but j characters remain in s2. We must insert all remaining j + 1 characters.
  • Return: j + 1
• String s2 is exhausted (j < 0):
  • We have converted our string, but i + 1 excess characters remain in s1. We must delete all of them.
  • Return: i + 1

5. Transitioning to Memoization (Top-Down DP)

Because recursion recalculates identical subproblems repeatedly (overlapping subproblems), we cache states using a 2D DP table of size N x M.

Memoized Coded Solution (C++)

class Solution {
public:
    int f(int i, int j, string &s1, string &s2, vector<vector<int>> &dp) {
        // Base Cases
        if (i < 0) return j + 1;
        if (j < 0) return i + 1;

        if (dp[i][j] != -1) return dp[i][j];

        // Match condition
        if (s1[i] == s2[j]) {
            return dp[i][j] = f(i - 1, j - 1, s1, s2, dp);
        }

        // Mismatch condition: min of Insert, Delete, Replace
        int insertOp  = f(i, j - 1, s1, s2, dp);
        int deleteOp  = f(i - 1, j, s1, s2, dp);
        int replaceOp = f(i - 1, j - 1, s1, s2, dp);

        return dp[i][j] = 1 + min({insertOp, deleteOp, replaceOp});
    }

    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return f(n - 1, m - 1, word1, word2, dp);
    }
};

6. Converting to Tabulation (Bottom-Up DP)

To avoid recursion stack overflow and negative index bugs, we shift to 1-based indexing, mapping -1 states to 0.

• Table dimensions become (N + 1) x (M + 1).
• dp[0][j] = j and dp[i][0] = i.

Tabulation Code Implementation

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        // Base cases initialization
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int insertOp  = dp[i][j - 1];
                    int deleteOp  = dp[i - 1][j];
                    int replaceOp = dp[i - 1][j - 1];
                    dp[i][j] = 1 + min({insertOp, deleteOp, replaceOp});
                }
            }
        }
        return dp[n][m];
    }
};

7. Space Optimization (Two 1D Arrays)

Notice that computing the current row (i) only requires data from the current row (j-1 column) and the previous row (i-1 row states: j, j-1).

We can completely eliminate the 2D table and replace it with two 1D arrays: previous and curr.

Space-Optimized Code Implementation

class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        vector<int> previous(m + 1, 0);
        vector<int> curr(m + 1, 0);

        // Base case for row 0
        for (int j = 0; j <= m; j++) {
            previous[j] = j;
        }

        for (int i = 1; i <= n; i++) {
            curr[0] = i; // Base case: j = 0 for current row
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    curr[j] = previous[j - 1];
                } else {
                    int insertOp  = curr[j - 1];
                    int deleteOp  = previous[j];
                    int replaceOp = previous[j - 1];
                    curr[j] = 1 + min({insertOp, deleteOp, replaceOp});
                }
            }
            previous = curr;
        }
        return previous[m];
    }
};

Note on Maximum Space Optimization: Can we compress this down to a single 1D array? No. Because the transition relies on both previous[j-1] (diagonal) and previous[j] (top), a single array would overwrite values needed later in the same iteration. Two 1D arrays (previous and curr) represent the absolute limit of space optimization.

8. Summary and Key Takeaways

• Core Objective: Compute the minimum edits (Insert, Delete, Replace) required to transform string s1 into s2.
• Max Operations Upper Bound: $N + M$ steps are always sufficient via total deletion and insertion.
• Recursive Blueprint: If characters match, shrink both pointers with 0 cost. If they mismatch, take 1 + min(Insert, Delete, Replace).
• State Shift via 1-Based Indexing: Shifting indexes by +1 simplifies base cases and avoids negative array indices.
• Tabulation Strategy: Bottom-up filling loops from 1 to N and 1 to M.
• Space Complexity Reduction: Moving from an $O(N \times M)$ 2D matrix down to two $O(M)$ 1D arrays (previous and curr) optimizes memory footprint for production environments.