# Check if the given string is interleaving of two other strings

Given 3 strings, we need to determine if third string is interleaving of first and second string.

Example,

```STRING 1: AB
STRING 2: XY
STRING 3: XABY

OUTPUT: TRUE```

## Solution

First, we need to understand what interleaving means.

Suppose we are given two string AB and XY

Now, the strings that can be formed by interleaving of AB and XY are:

1. ABXY
2. AXBY
3. AXYB
4. XYAB
5. XABY
6. XAYB

As we can see, the order of string AB and XY is maintained, that is A comes before B and X comes before Y.

## Brute Force Solution

The brute force solution is very simple and straight forward. We use recursive calls to check all possible cases.

Check the algorithm and code for better understanding.

### Pseudo Code

``````i: string 1 index
j: string 2 index
k: string 3 index

N: string 1 length
M: string 2 length
L: string 3 length

FUNCTION CheckInterLeaving ( string1, string2, string3, i, j , k )

if i==N AND j==M && k==L THEN
return TRUE
END

bool condition1 = FALSE
bool condition2 = FALSE

IF string1[i] == string3[k] THEN
condition1 = CheckInterLeaving(string1, string2, string3, i + 1, j, k + 1)
END

IF string2[j] == string3[k] THEN
condition2 = CheckInterLeaving(string1, string2, string3, i, j + 1, k + 1)
END

return condition1 OR condition2

END FUNCTION``````

### Code

```#include<iostream>
using namespace std;

// returns true if s3 is formed by interleaving of s1, s2
bool CheckInterLeaving(string s1, string s2, string s3, int i, int j, int k) {

// if we have reached the end of all string
// return true
if (i == s1.length() && j == s2.length() && k == s3.length())
return true;

bool condi1, condi2;
condi1 = condi2 = false;

// first we check if s1[i] == s3[k]
// if the statement is true, we increment i and k
// and call the function recursively
if (i < s1.length() && k < s3.length() && s1[i] == s3[k]) {
condi1 = CheckInterLeaving(s1, s2, s3, i + 1, j, k + 1);
}

// then we check if s2[j] == s3[k]
// if the statement is true, we increment j and k
// and call the function recursively
if (j < s2.length() && k < s3.length() && s2[j] == s3[k]) {
condi2 = CheckInterLeaving(s1, s2, s3, i, j + 1, k + 1);
}

// we use 2 condition variables, condi1 and condi2 because
// in case s1[i] == s2[j], we have two choice
// we can either choose s[i] or s[j]
// we need to check both the cases seperately
// if one of them is true then it means
// we can form s3 from interleaving of s1 and s2
return condi1 || condi2;
}

int main()
{
string s1, s2, s3;
s1 = "ab";
s2 = "xy";
s3 = "axyb";

if (CheckInterLeaving(s1, s2, s3, 0, 0, 0)) {
cout << "s3 is interleaving string of s1 and s2" << endl;
}
else {
cout << "s3 is not interleacing string of s1 and s2" << endl;
}
}```

#### Output

``s3 is interleaving string of s1 and s2``

In the worst-case scenario, string 1, string 2, string 3 are made from a single character.
Example,
s1 = “aaa”
s2 = “aaaa”
s3 = “aaaaaaa”
In this case, on each function call we will have 2 choices, s1[i] or s2[j].

Time complexity: O(2m+n).
Space Complexity: O(n+m).
This is because the maximum depth of a recursive call is equal to the sum of the length of string 1 and string 2.

## Dynamic Programming Solution

### 2D Dynamic Programming solution

Suppose a 2D array dp[n][m], where n is the size of string 1 (s1) and m is the size of string 2 (s2).

dp[i][j] represent if string 3 (s3) from index 0 to i+j-1 can be obtained from interleaving of s1 from index 0 to i-1 and s2 from index 0 to j-1.

In simple words, dp[i][j] means if the prefix of length i+j of s3 is interleaving of the prefix of length i of s1 and prefix of length j of s2.

#### To calculate dp[i][j], we consider 3 cases

1. i == 0
It means there is no contribution of s1 in forming s3. Hence,
dp[i][j] = (s2[j-1] == s3[j-1]) && (dp[i][j-1])
The above statement means that if the jth character of s2 and s3 is equal and all the characters of s2 and s3 before j are also equal (that is dp[i][j-1] is true) then dp[i][j] is true.
2. j == 0
It means there is no contribution of s2 in forming s3. Hence,
dp[i][j] = (s1[i-1] == s3[i-1]) && (dp[i-1][j])
The above statement means that if the ith character of s1 and s3 is equal and all the characters of s1 and s3 before i are also equal (that is dp[i-1][j] is true) then dp[i][j] is true.
3. i > 0 AND j > 0
In this case, both s1 and s2 have contribution in s3.
dp[i][j] = ( (s1[i-1] == s3[i+j-1]) && dp[i-1][j] ) || ( (s2[j-1] == s3[i+j-1]) && dp[i][j-1] )
dp[i][j] is true in 2 cases:
1. If current last character of s1, s3 that is s1[i-1] and s3[i+j-1] are equal and s3 from index 0 to i+j-2 is interleaving of s1 from 0 to i-2 and s2 from 0 to j-1, that is dp[i-1][j] is true.
2. If current last character of s2, s3 that is s2[j-1] and s3[i+j-1] are equal and s3 from index 0 to i+j-2 is interleaving of s1 from 0 to i-1 and s2 from 0 to j-2, that is dp[i][j-1] is true.

#### Pseudo Code

``````i: string 1 index
j: string 2 index
k: string 3 index

N: string 1 length
M: string 2 length
L: string 3 length

Func 2D_DP ( s1, s2, s3 ) THEN

if N+M is not equal to K THEN
return FALSE
END

FOR i = 0 TO N DO
FOR j = 0 TO M DO
IF i==0 THEN
dp[i][j] = s1[j-1]==s3[j-1] AND dp[i][j-1]
END
ELSE IF i==0 THEN
dp[i][j] = s2[i-1]==s3[i-1] AND dp[i-1][j]
END
ELSE IF i>0 AND j>0 THEN
dp[i][j] =  (s1[i-1]==s3[i+j-1])&&dp[i-1][j]) OR ((s2[j-1]==s3[i+j-1])&&dp[i][j-1])
END
END INNER FOR
END OUTER FOR

return dp[N][M]

END FUNCTION``````

#### Code

```#include<iostream>
#include<vector>
using namespace std;

// returns true if s3 is formed by interleaving of s1, s2
bool CheckInterLeaving(string s1, string s2, string s3) {
int n, m;
n = s1.length();
m = s2.length();

// if s3 length is not equal to n+m
// then it's not possible to form s3
if (s3.length() != n + m) return false;

vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

// dp[0][0] is 1
// i=0 and j=0
// means s1 is empty, s2 is empty, s3 is empty
// hance we can form s3 using s1 and s2 since
// all strings are empty
dp[0][0] = 1;

// dp[i][j] is true if
// it is possible to form prefix of s3 of length i+j
// from prefix of s1 of length i and
// prefix of s2 of length j
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {

if (i == 0 && j > 0) {
// s1 : 0 length prefix, no contribution in s3
// s2 : jth length prefix
// s3 : jth length prefix
dp[i][j] = (s2[j - 1] == s3[j - 1]) && dp[i][j - 1];
}
else if (j == 0 && i > 0) {
// s1 : ith length prefix
// s2 : 0 length prefix, no contribution in s3
// s3 : ith length prefix
dp[i][j] = (s1[i - 1] == s3[i - 1]) && dp[i - 1][j];
}
else if (i > 0 && j > 0) {
// s1 : ith length prefix
// s2 : jth length prefix
// s3 : i+j length prefix
dp[i][j] = ((s1[i - 1] == s3[i + j - 1]) && dp[i - 1][j]) || ((s2[j - 1] == s3[i + j - 1]) && dp[i][j - 1]);
}

}
}
return dp[n][m];
}

int main()
{
string s1, s2, s3;
s1 = "ab";
s2 = "xy";
s3 = "axyb";

if (CheckInterLeaving(s1, s2, s3)) {
cout << "s3 is interleaving string of s1 and s2" << endl;
}
else {
cout << "s3 is not interleacing string of s1 and s2" << endl;
}
}```

#### Output

``s3 is interleaving string of s1 and s2``

Time Complexity: O(N*M).
Space Complexity: O(N*M).

### 1D Dynamic Programming solution

If you look careful, in 2D DP code, we are saving truth value for all i and j combinations. But in order to determine dp[i][j] we only require dp[i][j-1] or dp[i-1][j].

Hence, we can replace

• dp[i][j] with dp[j]
• dp[i-1][j] with dp[j], if you think carefully the last value stored in dp[j] is dp[i-1][j]
• and dp[i][j-1] with dp[j-1]

#### Pseudo Code

``````i: string 1 index
j: string 2 index
k: string 3 index

N: string 1 length
M: string 2 length
L: string 3 length

Func 2D_DP ( s1, s2, s3 ) THEN

if N+M is not equal to K THEN
return FALSE
END

FOR i = 0 TO N DO
FOR j = 0 TO M DO
IF i==0 THEN
dp[j] = s1[j-1]==s3[j-1] AND dp[j-1]
END
ELSE IF i==0 THEN
dp[j] = s2[i-1]==s3[i-1] AND dp[j]
END
ELSE IF i>0 AND j>0 THEN
dp[j] =  (s1[i-1]==s3[i+j-1])&&dp[j]) OR ((s2[j-1]==s3[i+j-1])&&dp[j-1])
END
END INNER FOR
END OUTER FOR

return dp[M]

END FUNCTION``````

#### Code

```#include<iostream>
#include<vector>
using namespace std;

// returns true if s3 is formed by interleaving of s1, s2
bool CheckInterLeaving(string s1, string s2, string s3) {
int n, m;
n = s1.length();
m = s2.length();

// if s3 length is not equal to n+m
// then it's not possible to form s3
if (s3.length() != n + m) return false;

vector<int> dp(m + 1, 0);

dp[0] = 1;

for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {

if (i == 0 && j > 0) {
dp[j] = (s2[j - 1] == s3[j - 1]) && dp[j - 1];
}
else if (j == 0 && i > 0) {
dp[j] = (s1[i - 1] == s3[i - 1]) && dp[j];
}
else if (i > 0 && j > 0) {
dp[j] = ((s1[i - 1] == s3[i + j - 1]) && dp[j]) || ((s2[j - 1] == s3[i + j - 1]) && dp[j - 1]);
}

}
}
return dp[m];
}

int main()
{
string s1, s2, s3;
s1 = "ab";
s2 = "xy";
s3 = "axyb";

if (CheckInterLeaving(s1, s2, s3)) {
cout << "s3 is interleaving string of s1 and s2" << endl;
}
else {
cout << "s3 is not interleacing string of s1 and s2" << endl;
}
}```

#### Output

``s3 is interleaving string of s1 and s2``

Time Complexity: O(N*M).
Space Complexity: O(M).

## Reference

https://en.wikipedia.org/wiki/Dynamic_programming