Interleaving string in Java
If the string Str3 contains all of the characters from Str1 and Str2, it is considered interleaving Str1 and Str2. Keep in mind that the order of all characters in individual strings is maintained.
Example 1
Input: Str1 = "ppqrr", Str2 = "wqqrp" and Str3 = "ppwqqrqrpr"
Output: String 3 is an interleaving string.
Explanation: "pp" (from Str1) + "wqqr" (from Str2) + "qr" (from Str1) + "p" (from Str2) + "r" (from Str1)
Example 2
Input: Str1 = "ffzjj", Str2 = "uzzjf", Str3 = "ffuzzzfjjj"
Output: String 3 is not an interleaving string.
Explanation: Str3 cannot be obtained by combining Str1 and Str2.
Problem Description
Given three strings, Str1, Str2, and Str3, develop a program that determines if Str3 is an interleaving of Str1 and Str2.
Problem-solving Approach
The following three ways can be used to solve the problem:
- Brute Force Approach
- Using 2D Dynamic Programming
- Using 1D Dynamic Programming
Brute Force Approach
In this technique, we must keep the following two factors in mind:
- If the first character of Str3 matches the first character of Str1, we forward to the next character in Str1 and Str3 and call the function repeatedly.
- If the first character of Str3 matches the first character of Str2, we forward to the next character in Str2 and Str3 and call the function repeatedly.
Steps to Resolve the Issue
- First, we examine the base case. If Str1, Str2, and Str3 are empty, return true since empty Str3 is a combination of Str1 and Str2.
- Return false if Str3 is empty or Str1 or Str2 is not. This indicates that length(Str3) is less than length(Str1) + length (Str2).
- If none of the preceding two circumstances is satisfied, go to the next two conditions:
- If Str3[0] == Str1[0], look for Str1[1...], Str2, and Str3[1...].
- If Str3[0] == Str2[0], then look for Str1, Str2[1...], and Str3[1...].
- Return true if any of the two possibilities becomes true; otherwise, return false.
Let's set the following strategy into action in a function.
bool isInterleaved( char[] S1, char S2, char S3)
{
//base Case: whenever all strings are empty.
if (not (len(S1) != 0 or len(S2) != 0 or len(S3) != 0) )
return true
if (len(S3) == 0)
return false
return ((S3[0] == S1[0]) and isInterleaved(S1 + 1, S2, S3 + 1))
or ((S3[0] == S2[0]) and isInterleaved(S1, S2 + 1, S3 + 1))
}
Complexity
The following solution has an O(n2) time complexity since each Str3 character has two alternatives. Because we did not consider recursion stack space in this technique, the space complexity is O(1).
Using 2D Dynamic Programming
First, make a 2D Boolean array called DP[]. It is a prefix of Str3 formed by the interleaving of prefixes of strings Str1 and Str2 with lengths (a+1) and (b+1), respectively.
In this array, DP[a][b] shows whether it is feasible to obtain a substring of length (a+b+2).
The DP table generally indicates whether str3 is interleaving at the (a+b)-th index when S1 is at the a-th position, and S2 is at the b-th index. The 0th index represents an empty string. The 0th index represents the empty string. We can therefore conclude:
- If str1 and str2 are both empty, str3 will also be empty. As a result, we might think of it as interleaving.
- Suppose just str1 is an empty string, the previous str2 position is interleaving, and the current str2 position character is the same as the str3 current position character. In that case, it will be regarded as interleaving.
- If str2 is empty, the same thing happens. When both str1 and str2 are not empty, we arrive at a, b from a-1, b, and if a-1, b is already interleaving and a and current str3 position are equal, they are interleaving string. If we get to a, b from a, b-1, and if a, b-1 is already interleaving, and b and the current str3 location are identical, then it is also interleaving.
Steps to resolve the problem
- Make a 2D boolean DP[] array with dimensions u+1 and v+1. Where u and n denote the lengths of Str1 and Str2.
- Fill up the DP table by comparing the characters of Str1, Str2, and Str3 in the appropriate order.
- Return DP[u][v]
InterleavingString.java
public class InterleavingString
{
public static boolean isInterleave(String s1, String s2, String s3)
{
if (s3.length() != s1.length() + s2.length())
{
return false;
}
boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
for (int a = 0; a <= s1.length(); a++)
{
for (int b = 0; b <= s2.length(); b++)
{
if (a == 0 && b == 0)
{
dp[a][b] = true;
}
else if (a == 0)
{
dp[a][b] = dp[a][b - 1] && s2.charAt(b - 1) == s3.charAt(a + b - 1);
}
else if (b == 0)
{
dp[a][b] = dp[a - 1][b] && s1.charAt(a - 1) == s3.charAt(a + b - 1);
}
else
{
dp[a][b] = (dp[a - 1][b] && s1.charAt(a - 1) == s3.charAt(a + b - 1)) || (dp[a][b - 1] && s2.charAt(b - 1) == s3.charAt(a + b - 1));
}
}
}
return dp[s1.length()][s2.length()];
}
public static void main(String args[])
{
System.out.println(isInterleave("ppqrr", "wqqrp", "ppwqqrqrpr"));
}
}
Output:
Complexity
The time and space complexity of the preceding technique is O(u*v). Where u and v are the lengths of the strings
Using 1D Dynamic Programming
The above technique has an O(u*v) time and space complexity. Where u and v are the string lengths, The method is the same as described earlier. The only difference is that we just utilized a 1D array to hold the results of the supplied string's prefixes, which we then processed. The benefit of utilizing a 1D array is that we only need to update the array's element dp[a] when necessary by using dp[a-1] and the previous value of dp[a].
InterleavingString .java
public class InterleavingString
{
public static boolean isInterleave(String s1, String s2, String s3)
{
if (s3.length() != s1.length() + s2.length())
{
return false;
}
boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
for (int a = 0; a <= s1.length(); a++)
{
for (int b = 0; b <= s2.length(); b++)
{
if (a == 0 && b == 0)
{
dp[a][b] = true;
}
else if (a == 0)
{
dp[a][b] = dp[a][b - 1] && s2.charAt(b - 1) == s3.charAt(a + b - 1);
}
else if (b == 0)
{
dp[a][b] = dp[a - 1][b] && s1.charAt(a - 1) == s3.charAt(a + b - 1);
}
else
{
dp[a][b] = (dp[a - 1][b] && s1.charAt(a - 1) == s3.charAt(a + b - 1)) || (dp[a][b - 1] && s2.charAt(b - 1) == s3.charAt(a + b - 1));
}
}
}
return dp[s1.length()][s2.length()];
}
public static void main(String args[])
{
System.out.println(isInterleave("ppqrr", "wqqrp", "ppwqqrqrpr"));
}
}
Output:
