Difficulty: Hard, Asked-in: Google, Amazon, Microsoft
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.
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.
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.
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).
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'.
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'.
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.
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.
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)}
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)
}
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.
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));
}
}
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.
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.
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))
#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];
}
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).
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.
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];
}
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).
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:
Here is the modified iterative structure:
At each iteration of the inner loop, iterate over the characters in strings X and Y.
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];
}
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.
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:
By keeping track of these three relative values, we can modify the iterative structure for filling the table as follows:
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 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.
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:
Enjoy learning, Enjoy problem-solving!