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 {

    static int[][] t = new int[501][501]; // As maximum length of word can be 500.

    public static 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 characters of word1
        if(n2==0)
            return n1;

        if(t[n1][n2]!=-1)
            return t[n1][n2];

        // If characters are same
        if(word1.charAt(n1-1) == word2.charAt(n2-1))
            return t[n1][n2] = editDistance(word1,word2,n1-1,n2-1);

        else{

            int x = Math.min(editDistance(word1,word2,n1-1,n2-1),editDistance(word1,word2,n1-1,n2)); // Replace, Delete
            t[n1][n2] = 1 + Math.min(x,editDistance(word1,word2,n1,n2-1)); // Insert
            return t[n1][n2];
        }
    }
    public int minDistance(String word1, String word2) {
        
        // E.g: word1: horse word2: ros
        int n1 = word1.length();
        int n2 = word2.length();

        // Initialization
        for(int i=0;i<=500;i++)
            Arrays.fill(t[i],-1);

        int ans = editDistance(word1,word2,n1,n2);
        return ans;
    }
}

Approach 2: Tabulation (Bottom-Up)

class Solution {

    public int minDistance(String word1, String word2) {
        
        int n = word1.length();
        int m = word2.length();

        int[][] t = new int[n+1][m+1];

        // Initialize 0th column
        for(int i=0;i<=n;i++)
            t[i][0] = i ;

        // Initialize 0th row
        for(int i=0;i<=m;i++)
            t[0][i] = i;

        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){

                // If characters are same
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    t[i][j] = t[i-1][j-1];
                }
                else{
                    int x = Math.min(t[i-1][j],t[i][j-1]); // Delete, Insert
                    t[i][j] = 1 + Math.min(x,t[i-1][j-1]); // Replace
                }
            }
        }
        return t[n][m];
    }
}

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.