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 can perform three operations on a string: 1) Insert a character, 2) Delete a character, and 3) Replace a character.
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.
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).
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).
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 (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.
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).
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!
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 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.
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) });
}
}
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)
)
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.
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.
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.
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:
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].
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);
}
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]
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).
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.
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];
}
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]
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).
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.
Here is the modified iterative structure:
At each iteration of the inner loop, we 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 = 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];
}
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]
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.
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:
By keeping track of these three 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];
}
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 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 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:
We have implemented the above search feature using this algorithm :)
Enjoy learning, Enjoy problem-solving!