Edit Distance

Thought Process

The Edit Distance problem requires finding the minimum number of operations (insert, delete, or replace) needed to convert one string into another. Here are two approaches:

Approach 1: Memoization (Top-Down) - Use a 2D auxiliary array to store intermediate results and avoid redundant calculations. If the characters at the current positions match, move to the next characters. If they don't match, consider all three operations (insert, delete, and replace) and choose the one with the minimum cost.

Approach 2: Tabulation (Bottom-Up) - Use a 2D DP table to store the minimum edit distance for all substrings. Initialize the table for base cases (empty strings). Fill the table by comparing characters and choosing the minimum cost among the three operations.

Approach 1: Memoization (Top-Down)

class Solution {
public:
    // Auxiliary Array to store intermediate states
    int t[501][501];
    int editDistance(string word1, string word2, int n1, int n2){

        // We have to insert all characters of word2
        if(n1==0)
            return n2;
        
        // We have to delete all character of word1
        if(n2==0)
            return n1;
        
        if(t[n1][n2]!=-1)
            return t[n1][n2];

        if(word1[n1-1]==word2[n2-1])
            return t[n1][n2] = editDistance(word1,word2,n1-1,n2-1);
        else{
            int x = min(editDistance(word1,word2,n1,n2-1), editDistance(word1,word2,n1-1,n2)); // Insert, Delete
            return t[n1][n2] = 1 + min(x,editDistance(word1,word2,n1-1,n2-1)); // Replace
        }

    }
    int minDistance(string word1, string word2) {
        
        int n1 = word1.size();
        int n2 = word2.size();

        // Initialization
        for(int i=0;i<=n1;i++){
            for(int j=0;j<=n2;j++)
                t[i][j]=-1;
        }
        return editDistance(word1,word2,n1,n2);
    }
};

Approach 2: Tabulation (Bottom-Up)

class Solution {
public:
    int minDistance(string word1, string word2) {
        
        int n1 = word1.size();
        int n2 = word2.size();

        // Auxiliary Array to store intermediate states
        int t[n1+1][n2+1];

        for(int i=0;i<=n1;i++){

            for(int j=0;j<=n2;j++){

                if(i==0)
                    t[i][j] = j;

                else if(j==0)
                    t[i][j] = i;

                else if(word1[i-1]==word2[j-1])
                    t[i][j] = t[i-1][j-1];
                    
                else{

                    int x = min(t[i][j-1],t[i-1][j]); // Insert, Delete
                    t[i][j] = 1 + min(x,t[i-1][j-1]); // Replace
                }
            }
        }
        return t[n1][n2];
    }
};

Code Complexity

Time Complexity: O(n1 * n2)

Both approaches involve filling a 2D table of size n1 * n2, where n1 and n2 are the lengths of the input strings.

Space Complexity: O(n1 * n2)

Both approaches use a 2D auxiliary array to store intermediate results.