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[101][101] = {{ false }};
table[0][0] = 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.