Print all interleavings of given 2 string.

Print all interleaving of given 2 string.

---

Lets understand what is the input and the expected output.

Interleaved string contains all characters of string str1 and str2 and order of all characters in individual strings is preserved.
Example:
In Case 2, str1 = AB (B comes after A), str2 = MN(N comes after M).

So in interleaving of str1 and str2 this property should be maintained and all characters from str1 and str2 should be present in interleaving.

(It is not necessary that in interleaving string B should always be in adjacent to A, but B should occur after A only)

Algorithm

---

For String interleaving, 
we will keep picking one letter from string 1 in each recursive call until there is no letter remaining in string 1 and then we will keep picking one letter from string 2 in each recursive call until there is no letter remaining in string 2.


Lets understand with the help of example,
str1 = AB & str2 = MN, interleave =""

 
1. Pick one character from str1 and put it in interleave string
str1 = B & str2 = MN, interleave ="A"


2. Check is there any character remaining in String 1, Yes, repeat Step 1.
str1 =  & str2 = MN, interleave ="AB"

No more characters remaining in String 1, now repeat Step 1 for String 2 until is empty.
str1 =  & str2 = N, interleave ="ABM"

str1 =  & str2 = , interleave ="ABMN" 
(interleave string length became 4 that is str1.length + str2.length, So we got first interleave string.  print it)


Recursive call will be returned and reach at step where call for character B will be completed.
(str1 = B & str2 = MN, interleave ="A")
Since call for B is completed, now it will pick a letter from string 2 and next call will be.


(str1 = B  & str2 = N, interleave ="AM") and it continues.



Check below image for complete recursive stack trace.

Java Program to print all interleaving of Strings.

---

 

package javabypatel;

public class PrintAllInterleavingsOfGiven2Strings {

 public static void main(String[] args) {
  printAllInterleavings("AB", "XY", "");
 }
 
 private static void printAllInterleavings(String str1, String str2, String interleavingString){
  
  //If string 1 is null then print string 2 and return
  if(str1 == null){
   System.out.println(str2);
   return;
  }
  
  //If string 2 is null then print string 1 and return
  if(str2 == null){
   System.out.println(str1);
   return;
  }
  
  //if string 1 and string 2 length became 0, it means all characters from str1 and str2 is present in interleaving, print interleavingString.
  if(str1.length()==0 && str2.length()==0){
   System.out.println(interleavingString);
  }
  
  //pick characters from string 1 until string 1 length is empty.
  if(str1.length() != 0){
   //pick character from string 1 and append it in interleavingString string. In next recursive call remove picked character from string 1. 
   printAllInterleavings(str1.substring(1), str2, interleavingString + str1.charAt(0));
  }
  
  //pick characters from string 2 until string 2 length is empty.
  if(str2.length() != 0){
   //pick character from string 2 and append it in interleavingString string. In next recursive call remove picked character from string 2.
   printAllInterleavings(str1, str2.substring(1), interleavingString + str2.charAt(0));
  }
 }

}

Full stack trace to print all interleaving of Strings.

---

You may also like to see

---

Check whether a given string is an interleaving of two other given strings. (String 1 and String 2 contains unique characters)

---

Count trailing zeros in factorial of a number.

Swap two numbers In Java without using third variable - Best Approach.

Breadth First Search(BFS) Vs Depth First Search(DFS) with example in Java

Can static method be called using object in java

Method overriding and Method hiding Interview Question in Java.

When to use SOAP over REST Web Service. Is REST better than SOAP?.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.