Edit Distance (Levenshtein Distance) Editorial

Practice Problem Link: Practice Problem | Edit Distance

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given two strings s1 and s2. Find the minimum number of operations required to convert s1 to s2, where given operations are to insert, delete or replace a character.

Naive Approach

We can solve this problem by brute force recursion. Process the strings from their right ends, and compare them character by character. Now we have 2 choices: 

1. If the current character of both strings is the same, we can ignore them and recurse for n - 1, and m - 1 length of the string.
2. Else, consider we do all the operations on the first string, so we can:

• Insert a character and recurse for m and n - 1 length.
• Delete a character and recurse for m - 1 and n length.
• Replace a character and recurse for m - 1 and n - 1 length.

We can now calculate the minimum cost over all the possibilities and return it.

Analysis

• Time Complexity: O(3ⁿ)
• Space Complexity: O(1)

Implementation

C++

int editDistance(string s1, string s2, int m, int n) {
   if(m == 0) {
       return n;
   }
   if(n == 0) {
       return m;
   }
   if(s1[m - 1] == s2[n - 1]) {
       return editDistance(s1, s2, m - 1, n - 1);
   }
   return 1 + min({editDistance(s1, s2, m - 1, n), editDistance(s1, s2, m, n - 1), editDistance(s1, s2, m - 1, n - 1)});
}
int minOperations(string s1, string s2) {
   int m = s1.size();
   int n = s2.size();
   return editDistance(s1, s2, m, n);
}

Java

class Solution {
   int editDistance(String s1, String s2, int m, int n) {
       if(m == 0) {
           return n;
       }
       if(n == 0) {
           return m;
       }
       if(s1.charAt(m - 1) == s2.charAt(n - 1)) {
           return editDistance(s1, s2, m - 1, n - 1);
       }
       return 1 + min(editDistance(s1, s2, m - 1, n), editDistance(s1, s2, m, n - 1), editDistance(s1, s2, m - 1, n - 1));
   }
   int minOperations(String s1, String s2) {
       int m = s1.length();
       int n = s2.length();
       return editDistance(s1, s2, m, n);
   }
   int min(int a, int b, int c) {
       return Math.min(a, Math.min(b, c));
   }
}

Optimal Approach

We can observe that many function calls are being repeated and recalculated, again and again, ie there are many overlapping subproblems. This hints at using Dynamic Programming to memoize these overlapping subproblems. Here, the DP states are the Edit Distance for prefixes of length i and j for the strings.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

vector<vector<int>> dp;
int editDistance(string s1, string s2, int m, int n) {
   if(m == 0) {
       return n;
   }
   if(n == 0) {
       return m;
   }
   if(dp[m][n] != -1) {
       return dp[m][n];
   }
   if(s1[m - 1] == s2[n - 1]) {
       return dp[m][n] = editDistance(s1, s2, m - 1, n - 1);
   }
   return dp[m][n] = 1 + min({editDistance(s1, s2, m - 1, n), editDistance(s1, s2, m, n - 1), editDistance(s1, s2, m - 1, n - 1)});
}
int minOperations(string s1, string s2) {
   int m = s1.size();
   int n = s2.size();
   vector<vector<int>> temp(m + 1, vector<int>(n + 1, -1));
   dp = temp;
   return editDistance(s1, s2, m, n);
}

Java

class Solution {
   int dp[][];
   int editDistance(String s1, String s2, int m, int n) {
       if(m == 0) {
           return n;
       }
       if(n == 0) {
           return m;
       }
       if(dp[m][n] != -1) {
           return dp[m][n];
       }
       if(s1.charAt(m - 1) == s2.charAt(n - 1)) {
           return dp[m][n] = editDistance(s1, s2, m - 1, n - 1);
       }
       return dp[m][n] = 1 + min(editDistance(s1, s2, m - 1, n), editDistance(s1, s2, m, n - 1), editDistance(s1, s2, m - 1, n - 1));
   }
   int minOperations(String s1, String s2) {
       int m = s1.length();
       int n = s2.length();
       dp = new int[m + 1][n + 1];
       for(int i = 0; i <= m; i++) {
           Arrays.fill(dp[i], -1);
       }
       return editDistance(s1, s2, m, n);
   }
   int min(int a, int b, int c) {
       return Math.min(a, Math.min(b, c));
   }
}

Bottom-Up Approach

C++

int minOperations(string s1, string s2) {
   int m = s1.size();
   int n = s2.size();
   int dp[m + 1][n + 1];
   for(int i = 0; i <= m; i++) {
       for(int j = 0; j <= n; j++) {
           if(i == 0) {
               dp[i][j] = j;
           } else if(j == 0) {
               dp[i][j] = i;
           } else if(s1[i - 1] == s2[j - 1]) {
               dp[i][j] = dp[i - 1][j - 1];
           } else {
               dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
           }
       }
   }
   return dp[m][n];
}

Java

class Solution {
   int minOperations(String s1, String s2) {
       int m = s1.length();
       int n = s2.length();
       int[][] dp = new int[m + 1][n + 1];
       for(int i = 0; i <= m; i++) {
           for(int j = 0; j <= n; j++) {
               if(i == 0) {
                   dp[i][j] = j;
               } else if(j == 0) {
                   dp[i][j] = i;
               } else if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1];
               } else {
                   dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
               }
           }
       }
       return dp[m][n];
   }
   int min(int a, int b, int c) {
       return Math.min(a, Math.min(b, c));
   }
}