Edit Distance (Levenshtein Distance) Problem
Difficulty: Hard, Asked-in: Google, Amazon, Microsoft.
Let’s understand the problem
Write a program to find the minimum number of operations required to convert string X to string Y. You can perform three operations on a string: 1) Insert a character, 2) Delete a character, and 3) Replace a character.
- All of these operations have O(1) cost.
- Both X and Y consist of lowercase English letters.
Note: The edit distance between two strings is the minimum number of operations (insertion, deletion, or substitution of characters) required to transform one string into the other.
Example 1
Input: X[] = "cat", Y[] = "cut", Output: 1
Explanation: The first and last characters of both strings are the same, so we can convert "cat" to "cut" by replacing the 'a' with 'u'. The minimum number of operations required is 1 (one replace operation).
Example 2
Input: X[] = "horse", Y[] = "ros", Output: 3
Explanation: The characters 'o' and 's' are in the same order and common to both strings. To convert "horse" to "ros", we can replace 'h' with 'r' to get "rorse", then remove 'r' and 'e' to get "ros". So the minimum number of operations required is 3 (1 replace and 2 remove operations).
Example 3
Input: X[]= "sunday", Y[] = "saturday", Output: 3
Explanation: Last three and first characters of both strings are the same. To convert "sunday" to "saturday", we need to convert "un" to "atur". This requires three operations: replacing 'n' with 'r', inserting 't', and inserting 'a'.
Example 4
Input: X[] = "intention", Y[] = "execution", Output: 5
Explanation: Last four characters of both strings are the same. To convert "intention" to "execution", we need to convert "inten" to "execu". This requires five operations: replacing 'i' with 'e', replacing 'n' with 'x', removing 't', replacing 'n' with 'c', and inserting 'u'.
Discussed solution approaches
- Brute force recursive approach
- Efficient solution using top-down memoization
- Efficient solution using the bottom-up approach: using 2-D array
- Space-optimized bottom-up approach: using two 1-D arrays
- Space-optimized bottom-up approach: using one 1-D array
Brute force recursive approach
Solution idea
This is an optimization problem where solution space is very large i.e. there can be so many possible ways to convert one string to another string, but we need to find a solution using the minimum number of operations. So one basic approach is to explore all possible ways to perform the conversion and choose the one with the fewest number of operations.
When we need to consider all possibilities, we can try using recursive approach. To explore all possibilities recursively, we can start by comparing characters from the left or right end of both strings (suppose we are traversing from the right end).
There are two possibilities for each pair of characters : Either they are same or they are different. Note: Let's assume function editDistance(X, Y, m, n) returns the minimum number of operations to convert string X to string Y.
Case 1: If last characters of strings are equal i.e. if(X[m - 1] == Y[n - 1])
If last characters of the strings are same, we do not need to perform any operation. We can ignore last characters and recursively solve the same problem for remaining strings of size m - 1 and n - 1. In other words, the problem is reduced to finding the edit distance of the remaining substrings of input size m - 1 and n - 1 i.e. editDistance(X, Y, m - 1, n - 1).
Case 2: If last characters of strings are not equal i.e. if (X[m-1] != Y[n-1])
In this situation, we need to consider all three operations (insert, delete or replace) on the last character of the first string to make it equal to the last character of the second string.
Possibility 1: Suppose we insert an extra character that is equal to the last character of the second string. In this scenario, now problem get reduced to find the edit distance between the string X of size m and string Y of size n - 1. So we recursively call the same function with input size (m, n - 1) i.e. editDistance(X, Y, m, n - 1). The key question is: Why are we considering the string X of size m in the sub-problem? Think!
Possibility 2: If we delete the last character from the first string, now problem get reduced to find edit distance of string X of size m - 1 and string Y of size n. To solve this, we recursively call the same function for the input size (m - 1, n) i.e. editDistance(X, Y, m - 1, n).
Possibility 3: If we replace the last character of the first string with the last character of the second string, now problem get reduced to find edit distance of string X of size m - 1 to the string Y of size n - 1. To solve this, we recursively call the same function for the input size (m - 1, n - 1) i.e. editDistance(X, Y, m - 1, n - 1).
Now any one of the above possibilities will give the solution using the minimum number of operations. So we take a minimum of the value returned by the above three possibilities and add 1 to get the answer. In simple words: editDistance(m, n) = 1 + min { editDistance(m, n - 1), editDistance(m - 1, n), editDistance(m - 1, n - 1)}. Note: Why are we adding 1 here? Think and explore!
Overall recursive structure
if(X[m - 1] == Y[n - 1])
editDistance(X, Y, m, n) = editDistance(X, Y, m - 1, n - 1)
if(X[m - 1] != Y[n - 1])
editDistance(X, Y, m, n) = 1 + min
{ editDistance(X, Y, m - 1, n - 1),
editDistance(X, Y, m, n - 1),
editDistance(X, Y, m - 1, n)
}Base case
Base case occurs when one of the strings is empty. So if m is 0, we return n, and if n is 0, we return m. The reasoning behind this is simple: To transform one string into an empty string, we must delete all of its characters. Similarly, to transform an empty string into a non-empty string, we must insert all of the non-empty string's characters.
Solution code C++
int editDistance(string& X, string& Y, int m, int n)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (X[m - 1] == Y[n - 1])
return editDistance(X, Y, m - 1, n - 1);
else
{
return 1 + min({ editDistance(X, Y, m, n - 1),
editDistance(X, Y, m - 1, n),
editDistance(X, Y, m - 1, n - 1) });
}
}Solution code Python
def edit_distance(X, Y, m, n):
if m == 0:
return n
if n == 0:
return m
if X[m - 1] == Y[n - 1]:
return edit_distance(X, Y, m - 1, n - 1)
else:
return 1 + min(
edit_distance(X, Y, m, n - 1),
edit_distance(X, Y, m - 1, n),
edit_distance(X, Y, m - 1, n - 1)
)Time and space complexity analysis
Here input parameters are decreasing by 1 and recursion will stop when either m or n becomes 0. In the worst-case scenario, each recursive call will generate 3 more recursive calls.
- The height of the recursion tree will be the minimum of m and n (h = min(m, n)).
- At each recursive call, we are performing O(1) operation.
- So time complexity in the worst case = Total number of recursive calls = 1 + 3 + 3^2 + 3^3 + ... + 3^h = 3^(h+1) - 1 = O(3^h).
From another perspective: For every recursive call, if the last characters do not match, we will recursively explore three possibilities. In the worst case, we will end up exploring O(3^h) possibilities.
Space complexity is equal to the size of the recursion call stack, which is equal to the height of the recursion tree. Space complexity = O(h) = O(min(m, n)).
One of the reasons the time complexity is exponential is due to the presence of overlapping sub-problems. This means that the same sub-problems are repeatedly solved during recursion. We can observe this by analyzing the recursion tree diagram.
In the above diagram, several sub-problems are repeated. If we extend the recursion tree diagram further, we can observe more repeating sub-problems.
Efficient solution using top-down memoization
Solution idea
The critical question is: How can we optimize the time complexity? This is an optimization problem where sub-problems are repeated. So, we can think to apply the idea of dynamic programming.
One idea is to use the top-down approach of dynamic programming. In this approach, we will use a table to store solutions to subproblems and eliminate the need to recalculate the same subproblems multiple times. In other words, instead of solving the same subproblems repeatedly during recursion, we retrieve the solutions from the table if they have already been calculated.
Solution steps
Step 1: We first define a function editDistance(X, Y). Inside this: We find the lengths of strings X and Y and store them in variables m and n. Now we create a 2D table dp[m + 1][n + 1] to store the calculated edit distances for different subproblems. We also initialize all values with -1.
Note: We are storing all possible sub-problems in the table, which is equal to (m + 1)*(n + 1). The idea is simple: Both m and n are decreasing by 1 during the recursive calls and reaching the value 0. So m + 1 possibilities for the first parameter and n + 1 possibilities for the second parameter. Total number of possible subproblems = (m + 1)*(n + 1).
Step 2: Now we call a helper function editDistanceHelper(X, Y, m, n, dp) to find the edit distance between strings. Inside this: We first check base case conditions. If m == 0, return n and if n == 0 return m.
Step 3: Now we check if the edit distance for the current m and n values has already been calculated and stored at dp[m][n]. If yes, we return the stored value i.e. if (dp[m][n] != -1), return dp[m][n]. Otherwise, we calculate the solution recursively and store that value at dp[m][n].
Step 4: If (X[m - 1] == Y[n - 1]), we recursively call the editDistanceHelper(X, Y, m - 1, n - 1, dp) to calculate the edit distance without considering the last characters. We store the result in dp[m][n].
Step 5: If (X[m - 1] != Y[n - 1]), we recursively call editDistanceHelper for three cases:
- editDistanceHelper(X, Y, m, n - 1, dp): Calculate the edit distance by inserting a character into X.
- editDistanceHelper(X, Y, m - 1, n, dp): Calculate the edit distance by deleting a character from X.
- editDistanceHelper (X, Y, m - 1, n - 1, dp): Calculate the edit distance by replacing a character in X.
Step 6: After this, we calculate the minimum of these three values, add 1 to it (since we performed an operation), and store the result in dp[m][n]. Finally, we return the edit distance stored in dp[m][n].
Solution code C++
int editDistanceHelper(string& X, string& Y, int m, int n, vector<vector<int>>& dp)
{
if (m == 0)
return n;
if (n == 0)
return m;
if (dp[m][n] != -1)
return dp[m][n];
if (X[m - 1] == Y[n - 1])
dp[m][n] = editDistance(X, Y, m - 1, n - 1, dp);
else
{
dp[m][n] = 1 + min({ editDistanceHelper(X, Y, m, n - 1, dp),
editDistanceHelper(X, Y, m - 1, n, dp),
editDistanceHelper(X, Y, m - 1, n - 1, dp) });
}
return dp[m][n];
}
int editDistance(string& X, string& Y)
{
int m = X.length();
int n = Y.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
return editDistanceHelper(X, Y, m, n, dp);
}Solution code Python
def editDistanceHelper(X, Y, m, n, dp):
if m == 0:
return n
if n == 0:
return m
if dp[m][n] != -1:
return dp[m][n]
if X[m - 1] == Y[n - 1]:
dp[m][n] = editDistanceHelper(X, Y, m - 1, n - 1, dp)
else:
dp[m][n] = 1 + min(
editDistanceHelper(X, Y, m, n - 1, dp),
editDistanceHelper(X, Y, m - 1, n, dp),
editDistanceHelper(X, Y, m - 1, n - 1, dp)
)
return dp[m][n]Time and space complexity analysis
We are solving each sub-problem only once during the recursion. So time complexity = O(Total number of different sub-problems) * O(1) = O(mn). We are using a table of size O(mn) to store the solutions to the sub-problems. So space complexity = O(mn).
Efficient solution using the bottom-up approach: using 2-D array
Since we have identified that this is a dynamic programming problem, we can solve it efficiently using the bottom-up approach. Here we aim to calculate solutions to the smaller subproblems in an iterative way and store their result in a table. The critical question is: How do we build the solution in a bottom-up manner? Here are the steps:
Table structure: The state of smaller sub-problems depends on the input parameters m and n because at least one of them will decrease after each recursive call. So we need to construct a 2-D table Edit[][] to store the solution of the sub-problems.
Table size: The size of the 2-D table will be equal to the total number of different subproblems, which is equal to (m + 1)*(n + 1).
Table initialization: Before building the solution, we need to initialize the table with the smaller version of the solution i.e. base case. Here m = 0 and n = 0 is the situation of the base case, so we initialize first-column Edit[i][0] with i and first-row Edit[0][j] with j.
for (int i = 0; i <= m; i = i + 1)
Edit[i][0] = i;
for (int j = 0; j <= n; j = j + 1)
Edit[0][j] = j;Iterative structure to fill the table: Now, we define iterative structure to fill the table Edit[][] i.e. a relation by which we build the solution of the larger problem using the solution of smaller problems. We can easily define the iterative structure by using the recursive structure of the above recursive solution.
- if (X[i - 1] == Y[j - 1]), Edit[i][j] = Edit[i - 1][j - 1].
- if (X[i - 1] != Y[j - 1]), Edit[i][j] = 1 + min(Edit[i][j - 1], Edit[i - 1][j], Edit[i - 1][j - 1]).
for (int i = 1; i <= m; i = i + 1)
{
for (int j = 1; j <= n; j = j + 1)
{
if (X[i - 1] == Y[j - 1])
Edit[i][j] = Edit[i - 1][j - 1];
else
{
Edit[i][j] = 1 + min(Edit[i][j - 1], min(Edit[i - 1][j], Edit[i - 1][j - 1]);
}
}
}Returning final solution: After filling the table iteratively, our final solution gets stored at the bottom right corner of the 2-D table i.e. we return Edit[m][n] as an output.
Solution code C++
int editDistance(string X, string Y, int m, int n)
{
int Edit[m + 1][n + 1];
for (int i = 0; i <= m; i = i + 1)
Edit[i][0] = i;
for (int j = 0; j <= n; j = j + 1)
Edit[0][j] = j;
for (int i = 1; i <= m; i = i + 1)
{
for (int j = 1; j <= n; j = j + 1)
{
if (X[i - 1] == Y[j - 1])
Edit[i][j] = Edit[i - 1][j - 1];
else
{
Edit[i][j] = 1 + min(Edit[i][j - 1],
min(Edit[i - 1][j], Edit[i - 1][j - 1]);
}
}
}
return Edit[m][n];
}Solution code Python
def editDistance(X, Y, m, n):
Edit = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
Edit[i][0] = i
for j in range(n + 1):
Edit[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
Edit[i][j] = Edit[i - 1][j - 1]
else:
Edit[i][j] = 1 + min(Edit[i][j - 1], Edit[i - 1][j], Edit[i - 1][j - 1])
return Edit[m][n]Time and space complexity analysis
We are using two single loops to initialize the table and one nested loop to fill the table entries in a bottom-up fashion. So time complexity = O(m) + O(n) + O(mn) = O(mn). From another perspective, we are visiting each table entry only once and performing O(1) operation.
We are using table of size (m + 1)(n + 1). So space complexity = O(mn).
Space-optimized bottom-up approach: using two 1-D arrays
Solution idea
Can we think to optimize the space complexity further? Can we use 1D array to store the intermediate results? If we observe the above solution, we are filling the table in a row-wise fashion and just using 3 adjacent entries to fill the table at position (i, j) i.e. (i - 1, j), (i, j - 1) and (i - 1, j - 1). These three entries are present in the current row and the previous row.
Suppose we are using two 1D arrays, curRow[] and preRow[], to store the results for the previous row and the current row.
- Entry (i, j) will be stored at curRow[j].
- Entry (i, j - 1) will be stored at curRow[j - 1].
- Entry (i - 1, j) will be stored at prevRow[j].
- Entry (i - 1, j - 1) will be stored at prevRow[j - 1].
Here is the modified iterative structure:
- curRow[j] = preRow[j - 1], if (X[i - 1] == Y[j - 1]).
- curRow[j] = 1 + min(preRow[j - 1], curRow[j - 1], preRow[j]), if (X[i - 1] != Y[j - 1]).
Solution steps
- We create two 1D arrays, curRow[n + 1] and preRow[n + 1] with value 0.
- Now, we initialise all values of the prevRow with the base case i.e. preRow[j] = j.
- Now we run two nested loops: Outer loop from i = 0 to m to track each row, and inner loop from j = 0 to n to fill values in curRow using preRow.
-
At each iteration of the inner loop, we iterate over the characters in strings X and Y.
- If characters at the current position are the same, we set curRow[j] to preRow[j - 1].
- If characters are different, we set curRow[j] to 1 plus a minimum of preRow[j - 1], curRow[j - 1], and preRow[j].
- Before moving to the next iteration of the outer loop or at the end of every iteration of the inner loop, we fill preRow with zeros and then swap values of preRow and curRow, so that curRow becomes the new preRow and vice versa. This will help us to reuse arrays and avoid allocating new memory for each row.
- After the outer loop, pre[n] will store the edit distance between two strings. So we return this value.
Solution code C++
int editDistance(string X, string Y, int m, int n)
{
vector<int> pre1Row(n + 1, 0);
vector<int> curRow(n + 1, 0);
for (int j = 1; j <= n; j = j + 1)
preRow[j] = j;
for (int i = 1; i <= m; i = i + 1)
{
curRow[0] = i;
for (int j = 1; j <= n; j = j + 1)
{
if (X[i - 1] == Y[j - 1])
curRow[j] = preRow[j - 1];
else
curRow[j] = min(preRow[j - 1], min(curRow[j - 1], preRow[j])) + 1;
}
fill(preRow.begin(), preRow.end(), 0);
swap(preRow, curRow);
}
return preRow[n];
}Solution code Python
def editDistance(X, Y, m, n):
preRow = [0] * (n + 1)
curRow = [0] * (n + 1)
for j in range(1, n + 1):
preRow[j] = j
for i in range(1, m + 1):
curRow[0] = i
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
curRow[j] = preRow[j - 1]
else:
curRow[j] = min(preRow[j - 1], curRow[j - 1], preRow[j]) + 1
preRow = [0] * (n + 1)
preRow, curRow = curRow, preRow
return preRow[n]Time and space complexity analysis
We are using two nested loops. So the time complexity of the above approach is the same as the previous approach i.e. O(mn). We are using two 1-D tables of size n + 1 to store sub-problem solutions. So space complexity = O(n). This is a significant improvement compared to the previous approach.
Space-optimized bottom-up approach using one 1-D array
Solution idea
Now critical question is: Can we further optimize space complexity and solve this problem using only one 1-D array? Here is an insight! When updating values in each row using curRow[], we only need three values:
- currRow[j]: Calculated in the previous iteration and is equivalent to prevRow[j] or Edit[i - 1][j].
- currRow[j - 1]: Calculated in the previous iteration and is equivalent to prevRow[j-1] or Edit[i - 1][j - 1]. We can use a variable pre to track of this value from previous iteration.
- currRow[j - 1]: Calculated in the current iteration and is equivalent to curRow[j-1] or Edit[i][j - 1].
By keeping track of these three values, we can modify the iterative structure for filling the table as follows:
- curRow[j] = pre, if (X[i - 1] == Y[j - 1]).
- currRow[j] = 1 + min(pre, currRow[j], currRow[j - 1]), if (X[i - 1] != Y[j - 1]).
Solution code C++
int editDistance(string X, string Y, int m, int n)
{
int pre;
vector<int> curRow(n + 1, 0);
for (int j = 1; j <= n; j = j + 1)
curRow[j] = j;
for (int i = 1; i <= m; i = i + 1)
{
pre = curRow[0];
curRow[0] = i;
for (int j = 1; j <= n; j = j + 1)
{
int temp = curRow[j];
if (X[i - 1] == Y[j - 1])
curRow[j] = pre;
else
curRow[j] = min(pre, min(curRow[j - 1], curRow[j])) + 1;
pre = temp;
}
}
return curRow[n];
}Solution code Python
def editDistance(X, Y, m, n):
pre = 0
curRow = [0] * (n + 1)
for j in range(1, n + 1):
curRow[j] = j
for i in range(1, m + 1):
temp = curRow[0]
curRow[0] = i
for j in range(1, n + 1):
prev = curRow[j]
if X[i - 1] == Y[j - 1]:
curRow[j] = pre
else:
curRow[j] = min(pre, curRow[j - 1], curRow[j]) + 1
pre = prev
return curRow[n]Time and space complexity analysis
Time complexity of above approach is identical to the previous approach i.e. O(mn). In terms of space complexity, we are using a single 1-D table of size n + 1, so space complexity is still O(n). Although it may not be a significant improvement, there is still a small improvement compared to the previous approach.
Critical ideas to think!
- Instead of comparing the last character, can we solve this problem by comparing the first character?
- Can we modify the above approaches to also return the sequence of operations performed by the optimal solution?
- In the space-optimized approach using two 1D arrays, can we implement it using a two-row 2-D table?
- What would be the worst and best scenario of the brute force recursive approach?
- In terms of approach, how this problem looks similar to longest common subsequence problem? Explore and think!
- Can we think to implement the top-down approach using the hash table instead of the 2D table? If yes, then what would be the difference in terms of performance?
- In the top-down approach, what is the count of total number of recursive calls in the worst case?
- Compare the actual performance of top-down and bottom-up approaches for various input sizes.
Applications of edit distance in computer science
We use the edit distance algorithm in a wide range of applications in computer science, particularly in natural language processing, computational biology, and computer vision. Here are some specific examples of these applications:
- Spell Checking: To identify and correct errors in the spelling of words by comparing them to words in a dictionary. It can also find the closest matching word in a dictionary and suggest it as a correction.
- Speech Recognition: To identify spoken words, even if they are not spoken perfectly.
- Natural Language Processing (NLP): To match words or phrases in natural language text, word sense disambiguation, parsing, and machine translation.
- Computational Biology: To identify functionally similar sequences of DNA and proteins, even if they have many differences at the individual character level.
- Computer Vision: Identify and match patterns in images, object recognition and find similar images in large databases.
- Automated Testing: To compare the output of a system to the expected output in automated testing. This can help us to determine if a system is working correctly or not.
We have implemented the above search feature using this algorithm :)
Suggested coding questions to practice
- Shortest common supersequence
- Wildcard pattern matching
- Longest palindromic subsequence
- Maximum length of repeated subarray
Enjoy learning, Enjoy problem-solving!