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

Leave a Comment

Your email address will not be published. Required fields are marked *