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

Check whether a given string is an interleaving of two other given strings.
(Assume there is unique characters in both strings)

---

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, in interleave string, B comes before A and in original string str1 = AB (B comes after A)
So it is not interleaved.

Algorithm

---

For checking whether the given string is interleaving of String 1 and String 2, (assuming characters in String 1 and String 2 are unique and not repeated)
 
we will first check whether size of interleaved string is equal to string1 length + string2 length.
If No, then string is not interleaved and return.

If the size is equal then iterate through the given interleaved string and compare each character against string 1 and string 2. If it matches with either string 1 or string 2 then increment the pointers for next match in both matched strings.

If at any point, character in interleaved string is not matching with any of the given 2 strings then String is not interleaved.

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

Take 3 pointers (j, k, and i ), 
j pointing to first character in str1.
k pointing to first character in str2.
i pointing to first character in interleave string.
 
Pick first character from interleave string and match it with first character of str1.
if it is matching then increment j++ and i++;
if it is not matching then compare it with first character of str2.
if it is matching then increment k++ and i++;

if it is not matching with either str1 and str2, then given string is not interleaved of str1 and str2.

If first character is matched with either str1 or str2, then repeat the step for next character and so on until i, j and k reaches respective string length.

Check below image for complete recursive stack trace.

Java Program to print all interleaving of Strings.

---

 

package string;

public class CheckStringIsInterLeavingOfTwoStringsContainingNoDuplicates {

 public static void main(String args[]){
  String str1 = "ABC";
  String str2 = "XYZ";
  String str3 = "XAYZBC";
  
  System.out.println(isInterleaved(str1, str2, str3));
 }

 private static boolean isInterleaved(String str1, String str2, String strToCheck) {
  
  int i=0, j=0, k=0;
  
  if(str1.length() + str2.length() != strToCheck.length()){
   return false;
  }
  
  while(k < strToCheck.length()){
   
   if( i < str1.length() && str1.charAt(i) == strToCheck.charAt(k)){
    i++;
   
   }else if(j < str2.length() && str2.charAt(j) == strToCheck.charAt(k)){
    j++;
   
   }else{
    return false;
   }
   
   k++;
  }
  
  if(!(i == str1.length() && j == str2.length() && k == strToCheck.length())){
   return false;
  }
  
  return true;
 }
 
}

 

You may also like to see

---

Print all interleavings of given 2 string.

Enjoy !!!! 

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

Tweet

Subscribe to receive free email updates: