A string can be represented as a binary tree by partitioning it to two non-empty substrings recursively.
If you choose any non-leaf node and swap its two children, then the string formed is the scramble of the original string.
You have to determine if s2 is a scrambled string of s1.
Understanding the Problem:
Let's understand it through some examples.
Example 1:
In Figure 1, s1= "coder" and s2= "ercod". We see that by just swapping the two children "cod" and "er" with each other, we are able to obtain the string s2.
Hence, s2 is a scrambled string of s1.
Example 2:
Let s1= "pepcoder" and s2= "peerdcop".
We partition the string s1 as shown in figure 2.
Initially we swap the partitions of "cod" i.e. "co" and "d" and obtain "dco".
On swapping "dco" with "er" and then combining them, we get "erdco".
Then we again swap and combine the strings "p" and "erdco" to form "erdcop''.
At last we combine the strings "pe" and "erdcop" to obtain " peerdcop".
Hence we see s2 is a scrambled string of s1.
Reader, you must meditate on the fact that we can partition the string s1 in multiple ways as shown in figure 3, but we choose that partition which gives us the scrambled string.
Approach:
WHAT
We now study the approach for solving this problem.
You know that if the length of s1 and s2 is not the same, then they cannot be scrambled strings.
Also, if there is any character which is different in both the strings then s1 and s2 are not scrambled strings.
If we put a cut in the string s1 at some ith position, then s1 gets divided into left and right parts. We also put a cut in s2 at the same ith position.
We check if the left part of s2 is a scrambled string of the left part of s1. Similarly, we check if the right part of s2 is a scrambled string of the right part of s1.
If both these conditions are true, then s2 is a scrambled string of s1.
However, the above method doesn't include the situations when swapping is done.
If s1= "pepcoder" and s2= "pcoderpe", then s2 is obtained by simply swapping the s1 at the first level as shown below.
In this example, if we compare the left and right parts of s1 and s2 then we won't get the desired answer.
Hence, to include this possibility, we also need to check if the left part of s2 is a scrambled string of the right part of s1. Similarly, we check if the right part of s2 is a scrambled string of the left part of s1.
If both these conditions are true, then s2 is a scrambled string of s1.
HOW & WHY
METHOD 1
Reader, we try to write a recursive code for this problem.
BASE CASE: If s1 is equal to s2, then s2 will definitely be a scrambled string of s1.
To understand this code line, we consider the example in figure 6.
Here, s1= "great" and s2= "aterg". We put a cut after every index to explore every possible outcome.
P1: As previously discussed, we first compare the left part of s2 with the left part of s1 and the right part of s2 with the right part of s1.
P2: In the OR part, we first compare the left part of s2 with the right part of s1 and the right part of s2 with the left part of s1.
This is denoted by //2. For every partition, the "&&" part checks P1 and the "||" checks P2.
If these conditions are fulfilled then we return "true". Else "false" is returned.
However, if you run this program, then we see that for some cases, the time limit has exceeded.
So, we need to find an optimized solution.
Reader, you can also watch the solution video in case you have any doubts in Method 1.
Analysis
Time Complexity:
O(nn)
Space Complexity:
O(n)
METHOD 2
In this method we don't use the substring function.
Instead, we use 4 more variables in this method: si1, ei1, si2 and ei2 which denote starting index of s1, ending index of s1, starting index of s2 and ending index of s2 respectively.
import java.io.*;
import java.util.*;
public class Main {
public static boolean IsScramble2(String s1,String s2, int si1,int ei1,int si2,int ei2){
if(s1.substring(si1,ei1+1).equals(s2.substring(si2,ei2+1))){ //1
return true;
}
for(int i=0;i< ei1-si1;i++){ //2
if((IsScramble2(s1,s2,si1,si1+i,si2,si2+i)&&IsScramble2(s1,s2,si1+i+1,ei1,si2+i+1,ei2))|| (IsScramble2(s1,s2,si1,si1+i,ei2-i,ei2)&&IsScramble2(s1,s2,si1+i+1,ei1,si2,ei2-i-1))){ //3
return true;
}
}
return false;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
if(s1.length()!=s2.length()){
System.out.println("false");
return;
}
System.out.println(IsScramble2(s1,s2,0,s1.length()-1,0,s2.length()-1));
}
}
java;
true";
As in method 1 we compare the strings s1 and s2 by applying the substring function using the variables si1, ei1, si2 and ei2. If the strings are equal then we return "true".
We apply a for loop for the total number of cuts possible in s1 which will be equal to ei1-si1.
Similar to //2 of method 1, we apply the desired checks by using the starting and ending index instead of using a function of substring.
In case you have any difficulties in understanding this method, we recommend you to watch the solution video.
However, when we run this code, for some cases we again get the "time limit exceeded" error.
Analysis
Time Complexity:
O(n4)
Space Complexity:
O(n4)
Reader, guess what? We optimize the problem further.
METHOD 3
We try to use memorization in this method. Here, we use a 3D dp array to solve this problem.
Reader, in the previous method we used 4 extra variables si1, ei1, si2 and ei2. But we realize if we know the length of a string and its starting index, then we can directly calculate its ending index and don't need to consider extra variables ei1 and ei2.
Now, if we make a cut after the 4th index. Hence, here the starting index will be considered as 0 and the length is taken as 5 (for indices 0-4).
This is depicted in figure 7 along with the calls made for it.
Let's take a look at the code now.
import java.io.*;
import java.util.*;
public class Main {
public static boolean IsScramble3(String s1,String s2, int si1, int si2,int len,Boolean[][][]dp){
if(s1.substring(si1,si1+len).equals(s2.substring(si2,si2+len))){ //1
return true;
}
if(dp[si1][si2][len]!=null){ //2
return dp[si1][si2][len];
}
for(int k=1;k< len;k++){
if((IsScramble3(s1,s2,si1,si2,k,dp)&&IsScramble3(s1,s2,si1+k,si2+k,len-k,dp))|| (IsScramble3(s1,s2,si1,si2+len-k,k,dp)&&IsScramble3(s1,s2,si1+k,si2,len-k,dp))){ //3
dp[si1][si2][len]=true;
return true;
}
}
dp[si1][si2][len]=false; //4
return false;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
int n=s1.length();
if(s1.length()!=s2.length()){
System.out.println("false");
return;
}
System.out.println(IsScramble3(s1,s2,0,0,s1.length(),new Boolean[n][n][n+1]));
}
}
java;
true";
BASE CASE: If s1 and s2 are equal then simply "true" is returned.
BASE CASE: If the given cell of dp array is filled, then we return its value.
This code line has been discussed in Figure 7 and other methods.
However, here, we also store "true" against the given cell after it is used.
Later, we again store "false" against the current cell if we come out of the loop.
This method passes all the test cases and is our desired method.
We want you to watch the solution video to understand this method in-depth.
Analysis
Time Complexity:
O(n4)
Space Complexity:
O(n3)
We end this article here. We will further discuss the tabulation part of this problem in the next article. So don't forget to check it out too.
