CareerCup

It is called the String Shuffle Problem,
And it is hard one, the brute force solution takes O(2^n) , and a dynamic programming solution takes O(n^2).

bool f(char* s1, char* s2, char* s3)
{
    if(*s1 == '\0' && *s2 == '\0' && *s3 == '\0')
    {
        return true;
    }

    if (*s3 == '\0')
    {
        return false;
    }

    if (*s1 == '\0' && *s2 == '\0')
    {
        return false;
    }
    
    return ((*s1==*s3 && f(s1+1, s2, s3+1)) ||
            (*s2==*s3 && f(s1, s2+1, s3+1)));
}

lets say N=strlen(s1) + strlen(s2)

sort s3, and concat(s1,s2) ---- 2Nlog(N)
now compare(sorted s3, sorted concat(s1,s2)) --- N
(this step can be done in O(N) by keeping two iterators, one at the start and one at the end.)

So, the whole thing will be done in Nlog(N)

I think the solution to this problem is very simple.

Mantain 3 pointers

1. Point the first pointer to str3.second pointer to s1 and third pointer to s2.

2.Keep on incrementing str3 pointer.For each value,check whether the value at pointer is similar to str1 pointer or similar to str2.
if similar increment that pointer.
If not return false.

3.If at any point we encounter null at str1 pointer or str2 pointer,simply compare strcmp(str3 pointer,str1 or str2 pointer)

Complexity is O(1).

if both the pointr values are same then proceed with checking the next character.. till u find a character which is common in only one string pointer.

wat if we use count sort principle...i.e. determine freq of each char in s1 increase freq count as u run thru it den do d same for s2 and increase freq count in d same array...so d extra aaray used now contains addition of freqs of chars frm s1 and s2..now run thru s3 and as u run decrement the counts.....after u r done run thru the extra array that holds freq and at no point shd u get freq < 0

Vanda is right

Here is a recursive solution:-

bool does_interleave(string w1, string w2, string w3)
{
....size_t l1 = w1.size();
....size_t l2 = w2.size();
....size_t l3 = w3.size();

....if (l3 == 0 && (l1 != 0 || l2 != 0)) return false;

....if ((l1 == 0 && w2 == w3) || (l2 == 0 && w1 == w3)) {
........return true;
....} else {
........bool ret = false;
........if (w1[l1-1] == w3[l3-1]) ret = does_interleave(w1.substr(0,l1-1), w2, w3.substr(0, l3-1));
........if (!ret && w2[l2-1] == w3[l3-1]) ret = does_interleave(w1, w2.substr(0,l2-1), w3.substr(0, l3-1));
........return ret;
....}
}

@Vanda..
I think there is a flaw in your algo:-

say if word1 = abdg, word2 = dgc , word3 = abdgcdg
if i am not wrong, your algo wud successfully compare till
word1 = null and word = dgc and word3 = cdg. Then compare dgc and cdg and return false. But this case is actually a "TRUE" return case.
ab"dgc"dg

Think over...

Thanks,
Rohith Menon.

guys, let's consider the following fact:
I keep countArr[128] and initialize it with all '0' now parse down
all s1 and s2 and increment count in countArr. like countArr[s1[i]]++
now parse down s3 and decrement countArr[s3[i]]--;
after this, if all items of countArr are not 0 then s3 can't be formed with s1 and s2.
However even if it is 0 then it does not imply s3 can be formed. The
condition I have checked in necessary but not sufficient :( because
if s3 is taken out in random order from s1 and s2 then also the above
condition will be satisfied, but s3 will not be the desired one!

arnab your algorithm will work with a minor change. you can initialize the array with data from S3 first and then use S1 and S2 to decrement the counters. If at the end the entire array has 0's, then you got your answer.

Ikonos / Arnab ,
How will you ensure the order ?

The idea from Vandna is something that strikes my mind after reading the question. Vandna's approach is correct provided we never end up in a situation where we've a particular character that appears in both of the strings and we're stuck as to which one is the correct one.

how about to check whether the given sequence is a subsequence of the concatenated string of s1 and s2 , i guess this sure will solve the problem

how about to check whether the given sequence is a subsequence of the concatenated string of s1 and s2 , i guess this sure will solve the problem

Here is the idea behind getting an algorithm in O(m+n), where m and n are the lengths of the two strings s1 and s2, such that s1+s2+s3, where + represents this strange concatenation.

Imagine a matrix with m columns and n rows. each column is labeled by a symbol in string s1, and each row is labeled by a character in string s2. If you draw it, look at where the vertical lines intersect the horizontal lines, and call these points. These intersections are the points of interest. The question becomes: if you start in the upper left point and you can only go right and down, can you reach the lower right corner? A move is valid only if the segment corresponding to the current character is the character in s3. If you start labeling the points with true if you can reach that point and with false otherwise (exploring false points is not interesting). First, label all the top points, then all the left points. Now start labeling the second row of points (left to right), then the next row, and so on.

If you can label the lower right point with true, them s1+s2=s3. Note that to actually find the correct interleaving, you need an auxiliary structure with back pointers.

Here is the idea behind getting an algorithm in O(m+n), where m and n are the lengths of the two strings s1 and s2, such that s1+s2+s3, where + represents this strange concatenation.

Imagine a matrix with m columns and n rows. each column is labeled by a symbol in string s1, and each row is labeled by a character in string s2. If you draw it, look at where the vertical lines intersect the horizontal lines, and call these points. These intersections are the points of interest. The question becomes: if you start in the upper left point and you can only go right and down, can you reach the lower right corner? A move is valid only if the segment corresponding to the current character is the character in s3. If you start labeling the points with true if you can reach that point and with false otherwise (exploring false points is not interesting). First, label all the top points, then all the left points. Now start labeling the second row of points (left to right), then the next row, and so on.

If you can label the lower right point with true, them s1+s2=s3. Note that to actually find the correct interleaving, you need an auxiliary structure with back pointers.

int p1,p2,p3
int c1[],c2[],c3[], cp;

p1=p2=p3=0;
cp=0;

while(true)
{
  if(s3[p3]=='\0')
  { 
    if(s2[p2]!='\0' || s1[p1]!='\0')
    {  
      if(cp>0)
      { 
        //backtrack
        p1=c1[cp-1];
        p2=c2[cp-1];
        p3=c3[cp-1];
        cp--;
        p3++;
        p2++;
      }
      else
      {
        return false; 
      }
    }
  }

  if(s3[p3]==s1[p1] && s3[p3]!=s2[p2])
  {
    p3++;
    p1++;
  }  
  else if(s3[p3]==s2[p2] && s3[p3]!=s1[p1])
  {
    p1++;
    p3++;
  }
  else if(s3[p3]==s1[p1] && s3[p3]==s2[p2])
  {
    c1[cp]=p1;
    c2[cp]=p2;
    c3[cp]=p3;
    p1++;
    p3++;
    cp++;
  }
  else
  {
    if(cp>0)
    { 
      //backtrack
      p1=c1[cp-1];
      p2=c2[cp-1];
      p3=c3[cp-1];
      cp--;
      p3++;
      p2++;
    }
    else
    {
      return false; 
    }
  }
}

How about the following approach?

 if ( len(s3) != len(s1) + len(s2))
   return FALSE;
 if(LCS(s1,s3) != s1)
   return FALSE;
 if(LCS(s2,s3) != s2)
   return FALSE;

return TRUE;

BOOL
IsInterleave(char *S1,char *S2,char *S3)
{
  BOOL Ret;

  printf("S1 = %s,S2 = %s, S3 = %s\n",S1,S2,S3);

  if(*S1 == '\0' && *S2=='\0' && *S3== '\0')
    return TRUE;

  if(*S1 == *S3)
    {
      Ret = IsInterleave(++S1,S2,++S3);
      if(Ret)
	return TRUE;
    }
  if(*S2 == *S3)
    {
      Ret = IsInterleave(S1,++S2,++S3);
      if(Ret)
	return TRUE;
    }
  return FALSE;
}

counting sort variation is best for such cases .... if space is not the issue....

This code 'll work for all the cases:

#include<iostream>
using namespace std;
bool compare(char *s1, char *s2, char *s3)
{
     bool x=false,y=false;
     if(!*s1 && !*s2 && !*s3)
     {
            return true;
     }
     if((*s1 || *s2) && !*s3)
     {
            return false;
            
     }
     if(*s1)
     {
         if(*s1 == *s3)
         {
                s1++;
                s3++;
                x = compare(s1,s2,s3);
         }
     }
     if(*s2)
     {
         if(*s2 == *s3)
         {
                s2++;
                s3++;
                y  = compare(s1,s2,s3);
         }
     }
     //cout<<x<<"  "<<y<<endl;
     if(x || y)
     {
          return true;
     }
     else
     {
         return false;
     }
          
     
}
int main()
{
    char str1[] = "abcab";
    char str2[] = "abdab";
    char str3[] = "ababcdabab";
    bool find = compare(str1,str2,str3);
    if(find)
    {
            cout<<"Interleaving is done.\n";
    }
    else
        cout<<"Interleaving is not done\n";
    return 0;
}

it is a simple problem and can be done in O(m*n) where m and n arre size of string s1 and string s2 respectively.

here's hint
use longest common subsequence algorithm (dynamic programming) on s1 and s3 mark characters in s3 which are matched with s1. now remaing string of s3 can be compared to s2 if they are same then accept else reject. (O(n) +O(m*n))

let me know if I am wrong...

def is_interleaved(string, s1, s2):

    if len(string) != len(s1) + len(s2):
        # No way we can be interleaved
        return False

    if string == s1 + s2 or string == s2 + s1:
        # Will capture case where string is one or two letters
        return True

    letter = string[0]
    letter_1 = s1[0] if len(s1) > 0 else ""
    letter_2 = s2[0] if len(s2) > 0 else ""

    result_1 = False
    result_2 = False
    if letter == letter_1:
        result_1 = is_interleaved(string[1:], s1[1:], s2)
    if letter == letter_2:
        result_2 = is_interleaved(string[1:], s1, s2[1:])
    return result_1 or result_2

Code form of Stefan algorithm
///
public static boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0) {
return true;
} else if (s3.length() != s1.length() + s2.length()) {
return false;
}
boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];



for (int s1Index = 0; s1Index <= s1.length(); ++s1Index) {
for (int s2Index = 0; s2Index <= s2.length(); ++s2Index) {
isInter[s1Index][s2Index] = (s1Index == 0 && s2Index == 0)
|| (s1Index > 0 && s1.charAt(s1Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index-1][s2Index])
|| (s2Index > 0 && s2.charAt(s2Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index][s2Index-1]);
}
}
return isInter[s1.length()][s2.length()];
} \\\

Code form of Stefan algorithm

public static boolean isInterleave(String s1, String s2, String s3) {
		if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0) {
			return true;
		} else if (s3.length() != s1.length() + s2.length()) {
			return false;
		}
		boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];



		for (int s1Index = 0; s1Index <= s1.length(); ++s1Index) {
			for (int s2Index = 0; s2Index <= s2.length(); ++s2Index) {
				isInter[s1Index][s2Index] = (s1Index == 0 && s2Index == 0)
						|| (s1Index > 0 && s1.charAt(s1Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index-1][s2Index])
						|| (s2Index > 0 && s2.charAt(s2Index-1) == s3.charAt(s1Index+s2Index-1) && isInter[s1Index][s2Index-1]);
			}
		}
		return isInter[s1.length()][s2.length()];
	}