This blog discusses a problem based on dynamic programming. Dynamic programming is one of the most asked concepts in programming contests and technical interviews. Dynamic Programming divides a problem into identical subproblems and solves each part to reach the final answer. In this blog, we will discuss the application of this concept in one such coding problem.
Problem Statement
Ninja has given you two strings, 'S1' and 'S2'. Your task is to modify 'S1' to make it equal to 'S2' using the given operations minimum number of times:
Insert: Insert a character at any position in 'S1'.
Remove: Remove a character from any position in 'S1'.
Replace: Replace a character with any other character in 'S1'.
Output minimum number of operations required to make 'S1' and 'S2' equal.
Input
Enter the first string: aabs
Enter the second string: xbs
Output
2
Explanation
We can delete the first character of ‘S1’ and replace the second character to ‘x’ to make 'S1' = 'S2'.
Input
Enter the first string: abcd
Enter the second string: abcd
Output
0
Explanation
Strings are already equal.
Approach 1
Let us understand the coding challenge in a bit detailed manner. Let ‘P1’ be the starting pointer for ‘S1’ and ‘P2’ be the starting pointer for ‘S2’. Now there are two cases that can occur-
S1[P1] == S2[P2]: In this case, we can simply go on to compare the next characters. In this case we will increment P1 and P2 by one.
S1[P1] != S2[P2]: In this case, we can use any of the three mentioned operations to match them.
Insert: Insert S2[P2] at the current position of S1. Now the task is to compare the characters pointed by P1 and P2 + 1.
Delete: Delete the current character pointed to by P1. Now the task is to compare the characters pointed by P1 + 1 and P2.
Replace: Replace the current character by S2[P2]. Now the task is to compare the characters pointed by P1 + 1 and P2 + 1.
As you can see we are generating similar subproblems in each of the cases where we compare different substrings of the given input strings.
Thus, we will use a recursive approach to solve this coding challenge. We will traverse the strings from the beginning. Let 'P1' and 'P2' be the current characters in 'S1' and 'S2', respectively. If 'P1' is not equal to 'P2', we can use any of the three operations mentioned in the problem statement to solve the problem. We will explore each of the three possibilities and take the minimum to solve the current inequality.
Algorithm
Take the input strings 'S1' and 'S2'.
Create a recursive function findMinChanges(string& s1, string& s2, int i,int j) where 'S1' and 'S2' are the input strings and i and j are pointers on 'S1' and 'S2' respectively.
If i == S1.length() return 'S2.length() - j' as we need to insert the rest of the characters in 'S2'.
If j == S2.length() return S1.length() - i as we need to delete the remaining characters in 'S1'.
If S1[i] == S2[j] return findMinChanges(s1, s2, i + 1, j + 1) as we have matched the ith character of ‘S1’ and jth character of ‘S2’;
Otherwise, do the following:
Assign 'X' = findMinChanges(s1, s2, i, j + 1) to signify the insert operation. On inserting the same character as S2[j], the next task is to compare ith character of ‘S1’ and (j+1)th character of ‘S2’;
Assign 'Y' = findMinChanges(s1, s2, i + 1, j) to signify the delete operation;
Assign 'Z' = findMinChanges(s1, s2, i + 1, j + 1) to signify the replace operation;
return 1 + min(X, Y, Z);
Program
#include <iostream>
#include <string>
using namespace std;
int findMinChanges(string &s1, string &s2, int i, int j)
{
// If any of the pointers have reached the end, return appropriate values.
if (i == s1.length())
{
return s2.length() - j;
}
if (j == s2.length())
{
return s1.length() - i;
}
// If the current characters match, no need of any operation.
if (s1[i] == s2[j])
{
return findMinChanges(s1, s2, i + 1, j + 1);
}
// Otherwise, any one of the insert, delete or replace operation needs to be performed.
// Insert operation.
int x = findMinChanges(s1, s2, i, j + 1);
// Delete operation.
int y = findMinChanges(s1, s2, i + 1, j);
// Replace operation.
int z = findMinChanges(s1, s2, i + 1, j + 1);
// Return after adding one to the answer.
return 1 + min(min(x, y), z);
}
int main()
{
// Take the input.
string s1, s2;
cout << "Enter the first string: ";
cin >> s1;
cout << "Enter the second string: ";
cin >> s2;
// Print the output.
cout << findMinChanges(s1, s2, 0, 0) << endl;
}
You can also try this code with Online C++ Compiler
Enter the first string: aabs
Enter the second string: xbs
Output
2
Time Complexity
The time of the above approach is O(3 ^ N), where 'N' is the length of 'S1'. It is because the recursive function spawns three calls of itself, giving rise to a 3-ary binary tree of recursive calls with total O(3 ^ N) nodes.
Space Complexity
The space complexity of the above approach is O(N), where 'N' is the length of 'S1'. It is because the size of the recursive stack can be at most O(N).
Approach 2
Let’s consider an example. Let ‘S1’ = ‘abcc’ and ‘S2’ = ‘evxcs’. In this case, there are two possible paths through which we will face the same subproblem.
Path 1 Replace ‘a’ with ‘e’ -> Replace ‘b’ with ‘v’
Through both these paths, we reach the subproblem where we compare “cc” with “xcs”. Hence we are computing the same value multiple times in the previous solution. Therefore, in this approach, we will use recursion with memoization to store the solution of subproblems as we encounter them. DP with memoization is a well-known technique to prevent this kind of recomputation.
Algorithm
Take the input strings 'S1' and 'S2'.
Create a 2-dimensional vector array 'DP[N + 1][M + 1] where 'N' is the size of 'S1' and M is the size of 'S2'.
Create a recursive function findMinChanges(string& s1, string& s2, int i,int j, vector<vector<int>>& dp) where 'S1' and 'S2' are the input strings and i and j are pointers on 'S1' and 'S2' respectively.
If i == S1.length() return DP[i][j] = 'S2.length() - j' as we need to insert the rest of the characters in 'S2'.
If j == S2.length() return DP[i][j] = S1.length() - i as we need to delete the remanining characters in 'S1'.
If S1[i] == S2[j] return DP[i][j] = findMinChanges(s1, s2, i + 1, j + 1);
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int findMinChanges(string &s1, string &s2, int i, int j, vector<vector<int>> &dp)
{
// Memoization step.
if (dp[i][j] != -1)
return dp[i][j];
// If any of the pointers have reached the end, return appropriate values.
if (i == s1.length())
{
return dp[i][j] = s2.length() - j;
}
if (j == s2.length())
{
return dp[i][j] = s1.length() - i;
}
// If the current characters match, no need of any operation.
if (s1[i] == s2[j])
{
return dp[i][j] = findMinChanges(s1, s2, i + 1, j + 1, dp);
}
// Otherwise, any one of the insert, delete or replace operation needs to be performed.
// Insert operation.
int x = findMinChanges(s1, s2, i, j + 1, dp);
// Delete operation.
int y = findMinChanges(s1, s2, i + 1, j, dp);
// Replace operation.
int z = findMinChanges(s1, s2, i + 1, j + 1, dp);
// Return after adding one to the answer.
return dp[i][j] = 1 + min(min(x, y), z);
}
int findMinOperations(string &s1, string &s2)
{
int n = s1.length();
int m = s2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
return findMinChanges(s1, s2, 0, 0, dp);
}
int main()
{
// Take the input.
string s1, s2;
cout << "Enter the first string: ";
cin >> s1;
cout << "Enter the second string: ";
cin >> s2;
// Print the output.
cout << findMinOperations(s1, s2) << endl;
}
You can also try this code with Online C++ Compiler
Enter the first string: aabs
Enter the second string: xbs
Output
2
Time Complexity
The time complexity of the above approach is O(N * M), where 'N' and 'M' are the lengths of 'S1' and 'S2', respectively. It is because it will take at most O(N * M) to fill the empty N * M positions of the 'DP' we have created.
Space Complexity
The time complexity of the above approach is O(N * M), where 'N' and 'M' are the lengths of 'S1' and 'S2', respectively. It is because of the size of the 'DP' array we have created.
Check out this video for a better understanding of the “Minimum Edit Distance” problem with proper code implementation.
Key Takeaways
We solved an interesting problem by using two approaches in this blog. We realised that the time complexity of the brute force approach is exponential and solved in almost linear time complexity using the dynamic programming approach. Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
8+ registered 