Edit Distance

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

Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Example 2:

Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

Approach - Bottom Up

• Use reverse memoization for reference

class Solution {
    Integer[][] dp;
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        dp = new Integer[m+1][n+1];
 
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = i+j;
                else if (word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 + Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1]));
            }
        }
        return dp[m][n];
    }
}

Approach - Memoization

• Just memoize the below solution
• First solution for reverse recursion and second for forward notice how we compare i-1 and j-1 instead of i and j the reason is simple we started from length so we can’t compare them or rather we need to convert it to 0 based this would not be an issue in forward loop as we stop by the time we reach the out of bound

class Solution {
    Integer[][] dp;
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        dp = new Integer[m+1][n+1];
        return solve(word1, word2, m, n);
    }
 
    public int solve(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0)
            return i+j;
 
        if (dp[i][j] != null)
            return dp[i][j];
 
        if (s1.charAt(i-1) == s2.charAt(j-1))
            return dp[i][j] = solve(s1, s2, i-1, j-1);
        else {
            int insert = 1 + solve(s1, s2, i, j-1);
            int delete = 1 + solve(s1, s2, i-1, j);
            int replace = 1 + solve(s1, s2, i-1, j-1);
            return dp[i][j] = Math.min(insert, Math.min(delete, replace));
        }
    }
}

class Solution {
    Integer[][] dp;
    public int minDistance(String word1, String word2) {
        dp = new Integer[word1.length()+1][word2.length()+1];
        return solve(word1, word2, 0, 0);
    }
 
    public int solve(String s1, String s2, int i, int j) {
        if (i == s1.length())
            return s2.length() - j;
        else if (j == s2.length())
            return s1.length() - i;
 
        if (dp[i][j] != null)
            return dp[i][j];
 
        if (s1.charAt(i) == s2.charAt(j))
            return dp[i][j] = solve(s1, s2, i+1, j+1);
        else {
            int insert = 1 + solve(s1, s2, i, j+1);
            int delete = 1 + solve(s1, s2, i+1, j);
            int replace = 1 + solve(s1, s2, i+1, j+1);
            return dp[i][j] = Math.min(insert, Math.min(delete, replace));
        }
    }
}

Approach - Recursion

• It is simple just think about the options for all three and if matches no need to add 1 also if either is finished then what to do

class Solution {
    public int minDistance(String word1, String word2) {
        return solve(word1, word2, 0, 0);
    }
 
    public int solve(String s1, String s2, int i, int j) {
        if (i == s1.length())
            return s2.length() - j;
        else if (j == s2.length())
            return s1.length() - i;
 
        if (s1.charAt(i) == s2.charAt(j))
            return solve(s1, s2, i+1, j+1);
        else {
            int insert = 1 + solve(s1, s2, i, j+1);
            int delete = 1 + solve(s1, s2, i+1, j);
            int replace = 1 + solve(s1, s2, i+1, j+1);
            return Math.min(insert, Math.min(delete, replace));
        }
    }
}