# String Interleave

Given: 3 strings s1, s2 and s3.
Objective: To find out if the string s3 could be formed using characters from string s1 and s2.

Note : The order of characters taken from s1 and s2 to form string s3 should remain the same.

Example: Consider string s1 ( abc ), string s2 [ bca ] and string s3 “abbcca”
One way : String s3 can be formed as [ ( ab ) [ bc ] ( c ) [ a ] ]
other way : String s3 can be formed as [ ( a ) [ b ] ( b ) [ c ] ( c ) [ a ] ]

Dynamic programming approach

Base Case : An empty s3 can be formed using empty s1 and empty s2.

Consider substring of s1 of length 1 i.e ( a ).
Consider substring of s2 of length 1 i.e [ b ].
Using these substrings we could form a substring of length 2. Thus we try to see if a substring of s3 of length 2 i.e “ab” could be formed using ( a ) and [ b ].

Substring s1
( Row )
Substring s2
( Column )
Substring s3
a ( length 1 ) b ( length 1 ) ab ( length 2 )

We try to match the end character of substring s3 i.e b with either the end character of substring s1 or end character of substring s2.
If it does, then we need to check if the previous substring of s3 ( of length 1 ) could also be formed using the end character of either s1 or s2. This could easily be deduced from the dynamic programming table. Dynamic Programming : Program to check if the string s3 is an interleave of string s1 and s2.

``````#include<iostream>
#include<cstring>

using namespace std;

bool CheckInterleave (string s1, string s2, string s3) {

bool table = {{ false }};
table = true; // an empty s1, s2 can generate empty s3

if (s1.size() + s2.size() != s3.size())
return false;

if (s1.size() == 0) {
if (s2 == s3)
return true;
return false;
}

if (s2.size() == 0) {
if (s1 == s3)
return true;
return false;
}

for (int r=0; r<=s1.size(); r++) {
for (int c=0; c<=s2.size(); c++) {
if (r == 0 and c == 0) {
table[r][c] = true;
} else if (r == 0) { // Only look for characters in string s2
table[r][c] = (table[r][c-1] and (s2.at(c-1) == s3.at(c-1)));
} else if (c == 0) { // Only look for characters in string s1
table[r][c] = (table[r-1][c] and (s1.at(r-1) == s3.at(r-1)));
} else {
table[r][c] = ((table[r-1][c] and (s1.at(r-1) == s3.at(r+c-1))) or
(table[r][c-1] and (s2.at(c-1) == s3.at(r+c-1))));
}
}
}
// Table
cout << "==================================== " << endl;
for (int r=0; r<=s1.size(); r++) {
for (int c=0; c<=s2.size(); c++)
cout << table[r][c] << " ";
cout << endl;
}
cout << "==================================== " << endl;
return table[s1.size()][s2.size()];
}

int main() {

string s1("abc");
string s2("bca");
string s3("abbcca");

if (CheckInterleave (s1, s2, s3))
cout << "Yes. [" << s1  << "]" << " interleaved with [" << s2 << "] froms [" << s3 << "]" << endl;
else
cout << "No. [" << s1  << "]" << " interleaved with [" << s2 << "] does not form [" << s3 << "]." << endl;

return 0;
}
``````

Output

``````====================================
1 0 0 0
1 1 0 0
1 1 1 0
0 1 1 1
====================================
Yes. [abc] interleaved with [bca] froms [abbcca]
``````

Time complexity: O ( m⋅n ), where m is the length of string s1 and n is the length of string s2.
Space complexity: O ( m⋅n ), where m is the length of string s1 and n is the length of string s2.

Copyright (c) 2019-2022, Algotree.org.