What you do makes a difference, and you have to decide what kind of difference you want to make.
Interleaving Of Two Strings
Welcome Back Reader!
We hope that you are doing great with Dynamic Programming so far. In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Interleaving of Two Strings".
Before you move any further, it is advised that you give this problem a fair try.
In this problem you are given three strings: s1, s2 and s3.
All you have to do is find whether s3 is formed by interleaving of s1 and s2.
s3 is interleaving if it contains all characters of s1 and s2, and the order of all characters in individual strings is preserved.
Sample Input:
aabcc
dbbca
aadbbcbcac
Sample Output:
true
How?
aadbbcbcac is interleaving as it contains all characters of aabcc and dbbca, and order of all characters in individual strings has been preserved.
For more clarity of the question, watch this part of the video.
Approach 1 - Using Recursion:
This problem can be solved in multiple ways; let's solve it using recursion first.
The basic thought that comes to our mind is the one where we use two pointers, first pointer, 'i' pointing to the first character of string 1 and second pointer, 'j' pointing to the first character of string 2 initially.
Then we will make two recursive calls, first call will be made to a sub problem by incrementing i, if ith character of string 1 and (i+j)th character of string 3 are equal/same.
And a second call will be made to a sub problem by incrementing j, if the jth character of string 2 and (i+j)th character of string 3 are equal/same.
And if either of the calls returns true then we can also return true as the final answer for the current recursive call/function.
But if neither of the two conditions is true i.e. ith character of string 1 is not equal to (i+j)th character of string 3 and jth character of string 2 is not equal to (i+j)th character of string 3 then we will return false at the end.
And even if these conditions are true but both the recursive calls return false then also we need to return false.
Talking of base case; when i and j grow equal to the length of string 1 and string 2 respectively then we can return true.
Let's try to code this!
Base case has been defined; if at any instance 'i' becomes equal to the length of string 1 and 'j' becomes equal to the length of string 2 then we will return true.
Then check if 'i' is in range and if ith character of string 1 equals to (i+j)th character of string 3.
If yes, then make a recursive call for a sub problem with incremented 'i' and check if the call returns true or not. If it is true then return true.
Then check if 'j' is in range and if jth character of string 2 equals (i+j)th character of string 3.
If yes, then make a recursive call for a sub problem with incremented 'j' and check if the call returns true or not. If it is true then return true.
At last return false; which will cover the cases if both the conditions are false or if one of the conditions is false and the other condition's recursive call returns false or if both the condition's recursive calls return false.
For more clarity of this part; watch this part of the video.
Analysis
Time Complexity:
O(2^(s1.length() + s2.length()))
At max, (2^(s1.length() + s2.length())) calls will be made, making the time complexity O(2^(s1.length() + s2.length())).
Space Complexity:
O(1)
Since no extra space has been used therefore space complexity remains constant.
Approach 2 - Using Memorization:
Now let's solve it using memorization.
As we have seen and discussed this several times, memorization is just an extension of the recursion approach which is more time efficient.
In order to convert the recursion approach into a memorization approach we just need an extra parameter in the signature and a few extra steps.
First of all, we need to count the number of variables that change while making recursive calls. And in this case, there are two variables 'i' and 'j'. So we need a boolean dp of 2 dimensions in the signature of the recursive function.
And in order to make this dp come into action, we need to store the result of recursive calls at the dp[i][j], as soon as the calls return the value.
We also need to store false at dp[i][j], in case both the conditions (i.e. ith character of string 1 is not equal to (i+j)th character of string 3 and jth character of string 2 is not equal to (i+j)th character of string 3) are false.
But what is the point of storing these values in the dp? Well before making any recursive call, we will check if dp[i][j] stores some boolean value or not. And if it does then we will simply return the dp[i][j].
Let's try to code this!
Base case has been defined; if at any instance 'i' becomes equal to the length of string 1 and 'j' becomes equal to the length of string 2 then we will return true.
After that it is important that you check if there is a value present at dp[i][j] and if dp[i][j] is not null then simply return dp[i][j] without making any recursive call.
And if dp[i][j] would have been null then check if 'i' is in range and if ith character of string 1 equals to (i+j)th character of string 3.
If yes, then make a recursive call for a sub problem with incremented 'i' and store the result of the recursive call in a boolean variable f1.
Then store the value of f1 at dp[i][j].
If yes, then make a recursive call for a sub problem with incremented 'i' and check if the call returns true or not. If it is true then return true.
Then check if 'j' is in range and if jth character of string 2 equals (i+j)th character of string 3.
If yes, then make a recursive call for a sub problem with incremented 'j' and store the result of the recursive call in a boolean variable f2.
Then store the value of f2 at dp[i][j].
If yes, then make a recursive call for a sub problem with incremented 'j' and check if the call returns true or not. If it is true then return true.
And in case both the conditions are false then we need to store false at dp[i][j].
At last return false; which will cover the cases if both the conditions are false or if one of the conditions is false and the other condition's recursive call returns false or if both the condition's recursive calls return false.
For more clarity of the code, watch this part of the video.
Analysis
Time Complexity:
O(s1.length() * s2.length())
At max, s1.length() * s2.length() calls will be made, making the time complexity O(s1.length() + s2.length()).
Space Complexity:
O((s1.length() +1) * (s2.length() + 1))
A 2D array dp has been used of dimensions (s1.length() + 1) * (s2.length() + 1), making the space complexity O((s1.length() + 1) * (s2.length()) + 1).
Approach 3 - Tabulation:
The last approach that we will discuss uses tabulation.
In this approach, first of all we allocate the memory and then assign meaning to it.
In this case, we will need a boolean 2D array, which will represent string 1 by rows and string 2 by columns.
A cell, dp[i][j] will store a boolean value representing that whether substring (0 - (i+j-1)) of string 3 is interleaving of substring (0 - (i-1)) of string 1 and substring (0 - (j-1)) of string 2.
And in any cell, dp[i][j], first of all we will check if (i-1)th character of string 1 equals the (i+j-1)th character of string 3. And if the characters are equal then at dp[i][j], store the same value which is stored at dp[i-1][j]. Because now that the current characters are equal, the problem now depends on the previous/smaller problem.
After checking this, if the value at dp[i][j] is false then check if (j-1)th character of string 2 is equal to the (i+j-1)th character of string 3. And if the characters are equal then at dp[i][j], store the same value which is stored at dp[i-1][j].
It is also important that you handle the special cases when i and j are 0, otherwise it will give run time error of index out of bound.
When i and j both are 0, i.e. at dp[0][0], it represents the case if both, substring 1 and substring 2 are empty. And we can make a blank substring 3 with the interleaving of both these substrings. So we will store 'true' at dp[0][0].
When i is 0 and j varies, in such cases, check if (j-1)th character of string 2 and (i+j-1)th character of string 3 are equal and if yes then at dp[0][j] store the same value stored at dp[0][j-1] and if not then store 'false' at dp[0][j].
When j is 0 and i varies, in such cases, check if (i-1)th character of string 1 and (i+j-1)th character of string 3 are equal and if yes then at dp[i][0] store the same value stored at dp[i-1][0] and if not then store 'false' at dp[i][0].
ADVICE: Watch part this of the video to understand the tabulation approach with the help of an example.
Let's try to code this!
First of all define a 2D array, dp of dimensions ((s1.length() + 1 * s2.length() + 1)).
Then apply a nested for loop, in order to fill the complete dp matrix.
After that, handle the special cases first; when both i and j are 0, put true at dp[0][0].
After that, handle the case where only i is 0, check if (j-1)th character of string 2 and (i+j-1)th character of string 3 are equal and if yes then at dp[0][j] store the same value stored at dp[0][j-1] and if not then store 'false' at dp[0][j].
After that, handle the case where only j is 0, check if (i-1)th character of string 1 and (i+j-1)th character of string 3 are equal and if yes then at dp[i][0] store the same value stored at dp[i-1][0] and if not then store 'false' at dp[i][0].
In rest of the cases, for dp[i][j], first of all we will check if (i-1)th character of string 1 equals the (i+j-1)th character of string 3. And if the characters are equal then at dp[i][j], store the same value which is stored at dp[i-1][j]. Because now that the current characters are equal, the problem now depends on the previous/smaller problem.
After checking this, if the value at dp[i][j] is false then check if (j-1)th character of string 2 is equal to the (i+j-1)th character of string 3. And if the characters are equal then at dp[i][j], store the same value which is stored at dp[i-1][j].
At last, after completely filling the 2D matrix, the final result will be stored at dp[dp.length - 1][dp[0].length-1] so simply return this value.
For more clarity of the code, watch this part of the video.
Analysis
Time Complexity:
O((s1.length() +1) * (s2.length() + 1))
A nested for loop has been used to fill the 2D matrix dp whose dimensions are ((s1.length() + 1) * (s2.length()) + 1), which makes the time complexity O((s1.length() + 1) * (s2.length()) + 1).
Space Complexity:
O((s1.length() +1) * (s2.length() + 1))
A 2D array, dp has been used, of dimensions (s1.length() + 1) * (s2.length() + 1), making the space complexity O((s1.length() + 1) * (s2.length()) + 1).
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.nextLine();
String s2 = scn.nextLine();
String s3 = scn.nextLine();
if (s1.length() + s2.length() != s3.length()) {
System.out.println("false");
return;
}
//System.out.println(solution1(s1, s2, s3, 0, 0));
//System.out.println(solution2(s1, s2, s3, 0, 0, new Boolean[s1.length()][s2.length()]));
System.out.println(solution3(s1, s2, s3));
}
//Dynamic Programming
public static boolean solution3(String s1, String s2, String s3) {
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0 ; i < dp.length; i++) {
for (int j = 0 ; j < dp[0].length; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = s2.charAt(j - 1) == s3.charAt(i + j - 1) ? dp[i][j - 1] : false;
} else if (j == 0) {
dp[i][j] = s1.charAt(i - 1) == s3.charAt(i + j - 1) ? dp[i - 1][j] : false;
} else {
if (s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = dp[i - 1][j];
}
if (!dp[i][j] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = dp[i][j - 1];
}
}
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
//Memorization
public static boolean solution2(String s1, String s2, String s3, int i, int j, Boolean[][] dp) {
if (i == s1.length() && j == s2.length()) {
return true;
}
if (dp[i][j] != null){
return dp[i][j];
}
if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
boolean f1 = solution(s1, s2, s3, i + 1, j, dp);
dp[i][j] = f1;
if (f1) {
return true;
}
}
if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
boolean f2 = solution(s1, s2, s3, i, j + 1, dp);
dp[i][j] = f2;
if (f2) {
return true;
}
}
dp[i][j] = false;
return false;
}
//Recursion
public static boolean solution1(String s1, String s2, String s3, int i, int j) {
if (i == s1.length() && j == s2.length()) {
return true;
}
if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
if (solution(s1, s2, s3, i + 1, j)) {
return true;
}
}
if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
if (solution(s1, s2, s3, i, j + 1)) {
return true;
}
}
return false;
}
}
java;
true";
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
