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:
- ABXY
- AXBY
- AXYB
- XYAB
- XABY
- 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
- 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. - 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. - 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:- 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.
- 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