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 have the following three operations permitted on a string: 1) Insert a character 2) Delete a character 3) Replace a character.
- All of these operations have the same cost, O(1).
- Both X and Y consist of lowercase English letters.
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'. So minimum number of operations required is 1, which is 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 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 (assume 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 two 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.
Case 2: If last characters of strings are not equal i.e. if (X[m-1] != Y[n-1])
In this situation, we consider all three operations on the last character of the first string in order to make it equal to the last character of the second string.
Possibility 1: We perform an insert operation at the end of the first string.
Possibility 2: We perform a delete operation at the end of the first string.
Possibility 3: We perform a replace operation at the end of the first string.
Possibility 1: Suppose we add an extra character to the first string 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 remove 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).
Here, we recursively compute the minimum cost for the remaining substrings after each operation, take a minimum of three values and add 1 to get an answer. In simple words: editDistance(m, n) = 1 + min { editDistance(m, n - 1), editDistance(m - 1, n), editDistance(m - 1, n - 1)}
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
The base case occurs when one of the strings is empty. We check if either m or n is 0. 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. Alternatively, 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(char X[], char 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(min(editDistance(X, Y, m, n - 1),
editDistance(X, Y, m - 1, n)),
editDistance(X, Y, m - 1, n - 1));
}
}Time and space complexity analysis
In the worst case scenario, each recursive call results in 3 more recursive calls. So the depth of recursion tree is equal to the maximum of either m or n (h = max(m, n)). At each recursive call, we are performing O(1) operation. So time complexity in the worst case is 1 + 3 + 3^2 + 3^3 + ... + 3^h = 3^(h+1) - 1 = O(3^h).
From other perspective: For every pair of string1 and string2, if the characters do not match, we recursively explore three possibilities. In the worst case, if none of the characters matches, we will end up exploring O(3^h) possibilities.
Space complexity is equal to the size of recursion call stack, which is equal to the height of recursion tree. So space complexity = O(h).
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? One idea is to use top-down approach of dynamic programming to optimize the recursive approach. Here 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
- We declare 2D Edit[][] array as the memoization table to store solutions to subproblems.
-
We check if m and n are both non-zero. If they are, we check if last characters of X and Y are same. If they are same, we recursively solve smaller subproblem of finding the edit distance of two strings without their last characters and store this value at Edit[m] [n] for future reference.
if (X[m - 1] == Y[n - 1]) { if (Edit[m - 1][n - 1] == -1) Edit[m][n] = editDistance(X, Y, m - 1, n - 1) else Edit[m][n] = Edit[m - 1][n - 1] } -
If last characters of X and Y are different, we consider scenario of all three operations: Deleting the last character of X, inserting the last character of Y at the end of string X, or replacing the last character of X with the last character of Y. We calculate all these subproblems recursively and store their value in Edit[][] array for the future reference.
int subprob1 if (Edit[m - 1][n] != -1) subprob1 = Edit[m - 1][n] else subprob1 = editDistance(X, Y, m - 1, n) int subprob2 if (Edit[m][n - 1] != -1) subprob2 = Edit[m][n - 1] else subprob2 = editDistance(X, Y, m, n - 1) int subprob3 if (Edit[m - 1][n - 1] != -1) subprob3 = Edit[m - 1][n - 1] else subprob3 = editDistance(X, Y, m - 1, n - 1) Edit[m][n] = 1 + min(subprob1, min(subprob2, subprob3)) - Finally, we return value stored at Edit[m][n].
Solution code C++
#define MAX 100
int Edit[MAX][MAX];
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])
{
if (Edit[m - 1][n - 1] == -1)
Edit[m][n] = editDistance(X, Y, m - 1, n - 1);
else
Edit[m][n] = Edit[m - 1][n - 1];
}
else
{
int subprob1;
if (Edit[m - 1][n] != -1)
subprob1 = Edit[m - 1][n];
else
subprob1 = editDistance(X, Y, m - 1, n);
int subprob2;
if (Edit[m][n - 1] != -1)
subprob2 = Edit[m][n - 1];
else
subprob2 = editDistance(X, Y, m, n - 1);
int subprob3;
if (Edit[m - 1][n - 1] != -1)
subprob3 = Edit[m - 1][n - 1];
else
subprob3 = editDistance(X, Y, m - 1, n - 1);
Edit[m][n] = 1 + min(subprob1, min(subprob2, subprob3));
}
return Edit[m][n];
}Time and space complexity analysis
In worst-case, we only need to solve each sub-problem once. As input size (m, n) decreases by 1 during each recursion, recursion will terminate when input size reaches 0. As a result, total number of different sub-problems in the worst-case = (m + 1)(n + 1) = O(mn).
So time complexity = O(mn) * O(1) = O(mn). In addition, 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 solution to the smaller subproblems in 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 important 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 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). Think!
Table initialization: Before building the solution, we need to initialize 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 the 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 need to 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 in a bottom-up manner. 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];
}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. So, time complexity = (m + 1)(n + 1)*O(1) = O(mn).
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, improving the space complexity to O(n)? 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, respectively. Here:
- 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
- Initialize two 1D arrays, curRow[n + 1] and preRow[n + 1] with value 0.
- 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, iterate over the characters in strings X and Y.
- If characters at the current position are same, set curRow[j] to preRow[j - 1].
- If characters are different, set curRow[j] to 1 plus minimum of preRow[j - 1], curRow[j - 1], and preRow[j].
- Before moving to the next iteration of outer loop or at the end of every iteration of inner loop, fill preRow with zeros and then swap values of preRow and curRow so that curRow becomes the new preRow and vice versa. This allows us to reuse arrays and avoid allocating new memory for each row.
- After outer loop finishes, return pre[n]. This is the final value in preRow array and represents the edit distance between two strings.
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++)
preRow[j] = j;
for (int i = 1; i <= m; i++)
{
curRow[0] = i;
for (int j = 1; j <= n; j++)
{
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];
}Time and space complexity analysis
The time complexity of the above approach is 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 edit distance problem using only one 1-D array? Here is an insight!
When updating values in each row using curRow[], we only need to track following three values:
- The value stored at currRow[j], which was calculated in the previous iteration and is equivalent to prevRow[j] or Edit[i - 1][j] in previous solutions.
- The value stored at currRow[j - 1], which was calculated in the previous iteration and is equivalent to prevRow[j-1] or Edit[i - 1][j - 1] in previous solutions. We could use a variable pre to keep track of this value from the previous iteration.
- The value stored at currRow[j - 1], which was calculated in the current iteration and is equivalent to curRow[j-1] or Edit[i][j - 1] in previous solutions.
By keeping track of these three relative 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];
}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 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!
Applications of edit distance in computer science
We use 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: The Edit distance algorithm can be used to identify and correct errors in the spelling of words by comparing them to words in a dictionary. It can be used to find the closest matching word in a dictionary and suggest it as a correction.
- Speech Recognition: The Edit distance algorithm can be used to match spoken words to their written counterparts. It can be used to identify spoken words, even if they are not spoken perfectly.
- Natural Language Processing (NLP): The Edit distance algorithm is used to match words or phrases in natural language text. It is often used for tasks such as word sense disambiguation, parsing, and machine translation.
- Computational Biology: The Edit distance algorithm is used in sequence alignment to identify functionally similar sequences of DNA and proteins, even if they have many differences at the individual character level. This has applications in identifying new strains of viruses and cancer.
- Computer Vision: The Edit distance algorithm can be used to identify and match patterns in images. It can be used for object recognition and to find similar images in large databases.
- Automated Testing: The Edit distance algorithm can be used to compare the output of a system to the expected output in automated testing. This can be used to determine if a system is working correctly or not.
Suggested coding questions to practice
- Shortest common supersequence
- Wildcard pattern matching
- Longest palindromic subsequence
- Maximum length of repeated subarray
Enjoy learning, Enjoy problem-solving!