Print all interleavings of given two strings | GeeksforGeeks

Print all interleavings of given two strings | GeeksforGeeks

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different

An interleaved string of given two strings preserves the order of characters in individual strings. 

Let the length of str1 be m and the length of str2 be n. Let us assume that all characters in str1 and str2 are different. Let count(m, n) be the count of all interleaved strings in such strings. The value of count(m, n) can be written as following.

     count(m, n) = count(m-1, n) + count(m, n-1)
     count(1, 0) = 1 and count(0, 1) = 1

To print all interleavings, we can first fix the first character of str1[0..m-1] in output string, and recursively call for str1[1..m-1] and str2[0..n-1]. And then we can fix the first character of str2[0..n-1] and recursively call for str1[0..m-1] and str2[1..n-1]. Code from http://www.lixinglian.com/idea/?p=369

public void printInterleavings(String s1, String s2, String soFar) {
 if ((s1 == null || s1.length() == 0)
   && (s2 == null || s2.length() == 0))
  return;
 if (s1 == null || s1.length() == 0) {
  System.out.print(" " + soFar + s2 + " ");
  return;
 }
 if (s2 == null || s2.length() == 0) {
  System.out.print(" " + soFar + s1 + " ");
  return;
 }
 printInterleavings(s1.substring(1), s2, soFar + s1.charAt(0));
 printInterleavings(s1, s2.substring(1), soFar + s2.charAt(0));

}

Read full article from Print all interleavings of given two strings | GeeksforGeeks