Problem Statement
Given two strings start and target, you need to determine the minimum number of operations required to convert the string start into the string target. The operations you can use are:
- Insert a character: Add any single character at any position in the string.
- Delete a character: Remove any single character from the string.
- Replace a character: Change any single character in the string to another character.
The goal is to transform start into target using the fewest number of these operations.
Examples
Example 1:
Input: start = "planet", target = "plan"
Output: 2
Explanation:
To transform "planet" into "plan", the following operations are required:
1. Delete the character 'e': "planet" -> "plan"
2. Delete the character 't': "plan" -> "plan"
Thus, a total of 2 operations are needed.Example 2:
Input: Input: start = "abcdefg", target = "azced"
Output: 4
Explanation:
To transform "abcdefg" into "azced", the following operations are required:
1. Replace 'b' with 'z': "abcdefg" -> "azcdefg"
2. Delete 'd': "azcdefg" -> "azcefg"
3. Delete 'f': "azcefg" -> "azceg"
4. Replace 'g' with 'd': "azceg" -> "azced"
Thus, a total of 4 operations are needed.Different Approaches
1️⃣ Recursive Approach
For every index of string 'start'(S1), we have three options to match that index with string 'target'(S2).
- replace the character.
- remove the character.
- insert some character at that index.
Therefore, we can think in terms of string matching path as we have done already in previous questions. As there is no uniformity in data, there is no other way to find out than to try out all possible ways. To do so we will need to use recursion.
Steps to form the recursive solution:
- Express the problem in terms of indexes: We are given two strings. We can represent them with the help of two indexes i and j. Initially, i=n-1 and j=m-1, where n and m are lengths of strings S1 and S2. Initially, we will call f(n-1,m-1), which means the minimum number of operations required to convert string S1[0…n-1] to string S2[0…m-1].
- So, f(i, j) gives the minimum number of operations required to convert string S1[from index 0 to i] to S2[from index 0 to j].
- Try out all possible choices at a given index: Now, i and j represent two characters from strings 'start' and 'target' respectively. There are only two options, either the characters represented by i and j match or they don’t.
When the characters match: If(
S2[i] == S2[j]), we would not want to do any operations to make them match, so we will just decrement both i and j by 1 and recursively find the answer for the remaining string portion. Return 0+f(i-1,j-1).
- When the characters don’t match: If(
S1[i] != S2[j]) is true, then we have to do any of three operations to match the characters. We have three options, we will analyze each of them one by one.(Case 1) Inserting a character: Consider this example
Now if we have to match the strings by insertions, what would we do:
- We would have placed an ‘s’ at index 5 of S1.
- Suppose i now point to s at index 5 of S1 and j points are already pointing to s at index j of S2.
- Now, we hit the condition, where characters do match. (as mentioned in case 1).
Therefore, we will decrement i and j by 1. They will now point to index 4 and 1 respectively.
Now, the number of operations we did were only 1 (inserting s at index 5) but do we need to really insert the ‘s’ at index 5 and modify the string? The answer is simply NO. As we see that inserting a character (here ‘s’ at index 5), we will eventually get to the third step. So we can just return 1+ f(i,j-1) as i remains there only after insertion and j decrements by 1. We can say that we have hypothetically inserted character s.
(Case 2) Deleting a character: Consider the same example,
We can simply delete the character at index 4 and check from the next index.
Now, j remains at its original index and we decrement i by 1. We perform 1 operation, therefore we will recursively call 1+f(i-1,j).
(Case 3) Replacing a character: Consider the same example,
If we replace the character ‘e’ at index 4 of S1 with ‘s’, we have matched both the characters ourselves. We again hit the case of character matching, therefore we decrement both i and j by 1. As the number of operations performed is 1, we will return 1+f(i-1,j-1).
To summarize, these are the three choices we have in case characters don’t match:
- In case of insertion of character, return 1+f(i-1,j).
- In case of deletion of character, return 1+f(i,j-1).
- In case of replacement of character, return 1+f(i-1,j-1).
/*It is pseudocode and it is not related to any specific programming language */ f(i, j){ if(S1[i] == S2[j]){ return f(i-1, j-1) } else return 1 + min(f(i-1, j-1), f(i-1, j), f(i, j-1)) }
- Return the minimum of all choices: As we have to return the minimum number of operations, we will return the minimum of all operations.
- Base Cases: We are reducing i and j in our recursive relation, there can be two possibilities, either i becomes -1 or j becomes -1, i.e., we exhaust either S1 or S2 respectively.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/**
* Utility function to calculate the edit distance between two substrings.
*
* @param start The first string.
* @param target The second string.
* @param i Current index in the first string (start).
* @param j Current index in the second string (target).
* @param dp Memoization table to store intermediate results.
* @return The minimum number of operations required to convert start[0..i] to target[0..j].
*/
int calculateEditDistance(string& start, string& target, int i, int j, vector<vector<int>>& dp) {
// Base case: If the first string is exhausted, insert all remaining characters of the second string.
if (i < 0)
return j + 1;
// Base case: If the second string is exhausted, remove all remaining characters of the first string.
if (j < 0)
return i + 1;
// Return precomputed result if it exists.
if (dp[i][j] != -1)
return dp[i][j];
// If characters match, move to the next pair.
if (start[i] == target[j]) {
return dp[i][j] = calculateEditDistance(start, target, i - 1, j - 1, dp);
}
// If characters don't match, consider all possible operations:
// 1. Replace a character (move both indices).
// 2. Remove a character from start (move index i).
// 3. Insert a character into start (move index j).
return dp[i][j] = 1 + min(
calculateEditDistance(start, target, i - 1, j - 1, dp), // Replace
min(
calculateEditDistance(start, target, i - 1, j, dp), // Remove
calculateEditDistance(start, target, i, j - 1, dp) // Insert
)
);
}
public:
/**
* Function to calculate the minimum number of operations required to transform one string into another.
*
* @param start The first string.
* @param target The second string.
* @return The minimum number of operations required to transform start into target.
*/
int editDistance(string start, string target) {
int n = start.size();
int m = target.size();
// Create a DP table initialized with -1 for memoization.
vector<vector<int>> dp(n, vector<int>(m, -1));
// Start the recursive calculation with the last indices of both strings.
return calculateEditDistance(start, target, n - 1, m - 1, dp);
}
};
int main() {
// Input strings
string start = "horse";
string target = "ros";
// Create an instance of the Solution class.
Solution solution;
// Compute and print the result.
cout << "The minimum number of operations required is: "
<< solution.editDistance(start, target)
<< endl;
return 0;
}
Complexity Analysis:
- Time Complexity: Exponential .
- Space Complexity:
O(N+M), where N is the length of string S1 and M is the length of string S2. As we are using a recursion stack space(O(N+M)).
2️⃣ Memoization
If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.
In order to convert a recursive solution to memoization the following steps will be taken:
- Declare a dp array of size [n][m]: where n and m are the lengths of 'S1' and 'S2' respectively. As there are two changing parameters in the recursive solution, 'i' and 'j'. The maximum value 'i' can attain is (n-1) and 'j' can attain maximum value of (m-1). Therefore, we need 2D dp array.
- The dp array shows the calculations of the subproblems, initialize it with -1 to show that no subproblem is solved yet.
- While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
- Store the value of subproblem: Whenever, a subproblem is encountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/**
* Utility function to calculate the edit distance between two substrings.
*
* @param start The first string.
* @param target The second string.
* @param i Current index in the first string (start).
* @param j Current index in the second string (target).
* @param dp Memoization table to store intermediate results.
* @return The minimum number of operations required to convert start[0..i] to target[0..j].
*/
int calculateEditDistance(string& start, string& target, int i, int j, vector<vector<int>>& dp) {
// Base case: If the first string is exhausted, insert all remaining characters of the second string.
if (i < 0)
return j + 1;
// Base case: If the second string is exhausted, remove all remaining characters of the first string.
if (j < 0)
return i + 1;
// Return precomputed result if it exists.
if (dp[i][j] != -1)
return dp[i][j];
// If characters match, move to the next pair.
if (start[i] == target[j]) {
return dp[i][j] = calculateEditDistance(start, target, i - 1, j - 1, dp);
}
// If characters don't match, consider all possible operations:
// 1. Replace a character (move both indices).
// 2. Remove a character from start (move index i).
// 3. Insert a character into start (move index j).
return dp[i][j] = 1 + min(
calculateEditDistance(start, target, i - 1, j - 1, dp), // Replace
min(
calculateEditDistance(start, target, i - 1, j, dp), // Remove
calculateEditDistance(start, target, i, j - 1, dp) // Insert
)
);
}
public:
/**
* Function to calculate the minimum number of operations required to transform one string into another.
*
* @param start The first string.
* @param target The second string.
* @return The minimum number of operations required to transform start into target.
*/
int editDistance(string start, string target) {
int n = start.size();
int m = target.size();
// Create a DP table initialized with -1 for memoization.
vector<vector<int>> dp(n, vector<int>(m, -1));
// Start the recursive calculation with the last indices of both strings.
return calculateEditDistance(start, target, n - 1, m - 1, dp);
}
};
int main() {
// Input strings
string start = "horse";
string target = "ros";
// Create an instance of the Solution class.
Solution solution;
// Compute and print the result.
cout << "The minimum number of operations required is: "
<< solution.editDistance(start, target)
<< endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*M), where N is the length of string S1 and M is the length of string S2. There are N*M states therefore at max ‘N*M’ new problems will be solved. - Space Complexity:
O(N+M) + O(N*M), Where N is the length of string S1 and M is the length of S2. As we are using a recursion stack space(O(N+M)) and an array of size N*M.
3️⃣ Tabulation
In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:
- Declare a dp array of size [n][m]: where n and m are the lengths of 's' and 't' respectively. As there are two changing parameters in the recursive solution, 'i' and 'j'. The maximum value 'i' can attain is (n-1) and 'j' can attain maximum value of (m-1). Therefore, we need 2D dp array.
Setting Base Cases in the Array: In the recursive code, our base condition was when i < 0 or j < 0, but we can’t set the dp array’s index to -1. Therefore a hack for this issue is to shift every index by 1 towards the right.
- Therefore, we set the base condition (keep in mind 1-based indexing), we set the first column’s value as 1 and the first row as 1.
- Iterative Computation Using Loops: Initialize two nested for loops to traverse the dp array and following the logic discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations. Keeping in mind the shifting of indexes, as for example str1[ind1] will be converted to str1[ind1-1].
- Returning the answer: At last dp[n][m] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/**
* Function to calculate the minimum number of operations required to transform one string into another.
*
* @param start The first string.
* @param target The second string.
* @return The minimum number of operations required to transform start into target.
*/
int editDistance(string start, string target) {
int n = start.size();
int m = target.size();
// Create a DP table to store edit distances.
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// Initialize the first row and column.
for (int i = 0; i <= n; i++) {
dp[i][0] = i; // Deleting all characters from start.
}
for (int j = 0; j <= m; j++) {
dp[0][j] = j; // Inserting all characters of target.
}
// Fill in the DP table using the recurrence relation.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// If characters match, no additional cost.
if (start[i - 1] == target[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
// If characters don't match, consider the minimum cost among replace, insert, and delete operations.
else {
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
// The value at dp[n][m] contains the edit distance.
return dp[n][m];
}
};
int main() {
// Input strings.
string start = "horse";
string target = "ros";
// Create an instance of the Solution class.
Solution solution;
// Compute and print the result.
cout << "The minimum number of operations required is: "
<< solution.editDistance(start, target)
<< endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*M), where N is the length of string S1 and M is the length of string S2. There are two nested loops used to solve this problem. - Space Complexity:
O(N*M), Where N is the length of string S1 and M is the length of S2. As we are using an array of size N*M.
4️⃣ Space Optimization
If we observe the relation obtained in the tabulation approach, dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]). We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.
We will space optimize in the following way:
- Take two rows ‘prev’ and ‘cur’ and initialize it to the base condition.
- Now, at starting the prev row needs to be initialized with its column value. Moreover, the cur variable whenever declared should have its first cell as a row value.
- Next, implement the memoization logic and replace dp[i-1] with prev and dp[i] by cur in the tabulation code.
- After every inner loop execution, we set prev=cur, for the next iteration.
- At last, return prev[m] as our answer.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
/* Function to calculate the minimum number
of operations required to transform S1 into S2*/
int editDistance(string start, string target) {
int n = start.size();
int m = target.size();
/* Declare two arrays to store previous
and current row of edit distances*/
vector<int> prev(m + 1, 0);
vector<int> cur(m + 1, 0);
// Initialize the first row
for (int j = 0; j <= m; j++) {
prev[j] = j;
}
// Calculate edit distances row by row
for (int i = 1; i <= n; i++) {
// Initialize the first column of current row
cur[0] = i;
for (int j = 1; j <= m; j++) {
// If the characters match, no additional cost
if (start[i - 1] == target[j - 1]) {
cur[j] = prev[j - 1];
}
else {
// Take minimum of three choices:
cur[j] = 1 + min(prev[j - 1], min(prev[j], cur[j - 1]));
}
}
// Update the previous row with current row
prev = cur;
}
// The value at cur[m] contains the edit distance
return cur[m];
}
};
int main() {
string s1 = "horse";
string s2 = "ros";
//Create an instance of Solutoin sol;
Solution sol;
// Call the editDistance function and print the result
cout << "The minimum number of operations required is: " << sol.editDistance(s1, s2);
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*M), where N is the length of string S1 and M is the length of string S2. There are two nested loops used to solve this problem. - Space Complexity:
O(M), Where N is the length of string S1 and M is the length of S2. As we are using arrays of size M+1.