Edit Distance

Description

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));
        }
    }
}

---

Primary Approach: 2D Dynamic Programming ($O(M\times N)$ Time, $O(M\times N)$ Space)

Intuition

To solve 72. Edit Distance, define dp[i][j] as the minimum number of operations required to convert the prefix word1[0 ... i-1] to word2[0 ... j-1]:

1. Base Cases:
   • dp[i][0] = i: Converting word1[0 ... i-1] to an empty string requires i deletions.
   • dp[0][j] = j: Converting an empty string to word2[0 ... j-1] requires j insertions.
2. Transitions:
   • If characters match (word1[i - 1] == word2[j - 1]): No operation needed for this character:

$\text{dp}[i][j]=\text{dp}[i-1][j-1]$

• If characters differ (word1[i - 1] != word2[j - 1]): Take 1 operation plus the minimum of three choices:
  • Insert: $\text{dp}[i][j-1]+1$
  • Delete: $\text{dp}[i-1][j]+1$
  • Replace: $\text{dp}[i-1][j-1]+1$

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
 
        // Base cases
        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++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
 
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int insert = dp[i][j - 1];
                    int delete = dp[i - 1][j];
                    int replace = dp[i - 1][j - 1];
                    dp[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
                }
            }
        }
 
        return dp[m][n];
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Where $M$ and $N$ are the lengths of word1 and word2.
• Space Complexity: $O(M\times N)$ — To store the 2D DP matrix.

---

Alternative Approach: Space-Optimized DP ($O(M\times N)$ Time, $O(\min (M,N))$ Space)

Intuition

Calculating row i only requires values from the current row i and the previous row i - 1. We can reduce memory from 2D to a single 1D array by keeping track of the top-left diagonal entry (prevDiag = dp[i-1][j-1]) in a temporary variable.

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return minDistance(word2, word1);
        }
 
        int m = word1.length();
        int n = word2.length();
        int[] dp = new int[n + 1];
 
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }
 
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);
            int prevDiag = dp[0]; // Stores dp[i-1][j-1]
            dp[0] = i;           // Base case: dp[i][0] = i
 
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
                int temp = dp[j]; // Store old dp[i-1][j] before updating
 
                if (c1 == c2) {
                    dp[j] = prevDiag;
                } else {
                    dp[j] = 1 + Math.min(dp[j - 1], Math.min(dp[j], prevDiag));
                }
 
                prevDiag = temp;
            }
        }
 
        return dp[n];
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Loops through all subproblems.
• Space Complexity: $O(\min (M,N))$ auxiliary space — Uses a 1D array of size $\min (M,N)+1$.

---

Key Interview Discussion Points

• 3 Operations Mapping:
  • dp[i][j - 1] $\to$ Insert: Assumes inserting word2[j - 1] into word1.
  • dp[i - 1][j] $\to$ Delete: Assumes deleting word1[i - 1].
  • dp[i - 1][j - 1] $\to$ Replace: Assumes replacing word1[i - 1] with word2[j - 1].
• Levenshtein Distance: Mention to the interviewer that this is formally known as the Levenshtein Distance algorithm, heavily used in spell checking, bioinformatics (sequence alignment), and natural language processing.

---

Easy Memory Rule

“Match $\to$ dp[i-1][j-1] | Mismatch $\to$ 1 + min(Insert, Delete, Replace)!”