You are given three strings: a, b and i. Write a function that checks whether i is an interleaving of a and b.
String i is said to be interleaving string a and b, if:
len(i) = len(a) + len(b).
i only contains characters present in a or b.
i contains all characters of a. From a, any character a[index] should be added exactly once in i.
i contains all characters of b. From b, any character b[index] should be added exactly once in i.
Order of all characters in individual strings (a and b) is preserved.
Example One
Input:
a = "123"
b = "456"
i = "123456"
Output: True
Example Two
Input:
a = "AAB"
b = "AAC"
i = "AAAABC"
Output: True
Example Three
Input:
a = "AAB"
b = "AAC"
i = "AAABAC"
Output: True
Notes
Input Parameters: You will be given three strings a, b and i.
Strings can contain:
Small alphabets - a-z
Large alphabets - A-Z
Numbers - 0-9
Output: Return a boolean if i is an interleaving of a and b.
Constraints:
● 0
● 0
Solution
Brute force recursive solution
First character in i should match first character in a or first character in b.
* If it matches first character in a, try matching second character in i with second character in a or first character in b
* If it matches first character in b, try matching second character in i with second character in b or first character in a
* If it matches none of them, terminate with a false
Hence, keep recursing for the rest of the strings. This is an exponential solution, O(2^(len(a)+len(b))) as you can either pick a character from a or a character from b.
Optimal Solution
Convention: str[0 : x] = first x chars of str.
We can say that i[0 : (a_i + b_i)] is an interleaving of a[0 : a_i] and b[0 : b_i], if at least one of the below two is true:
1) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : (a_i - 1)] and b[0 : b_i]
and
- a[ai - 1] == i[ai + bi - 1].
or
2) - i[0 : (a_i + b_i - 1)] should be an interleaving of a[0 : a_i] and b[0 : (b_i - 1)]
and
- b[bi - 1] == i[ai + bi - 1].
We can use DP to keep track of the already calculated values. Have a look at the solution for more details.
Space Complexity:
O(len(a) * len(b))
Time Complexity:
O(len(a) * len(b))
// -------- START --------
bool doStringsInterleave(string a, string b, string i) {
if (a.length() + b.length() != i.length()){
return false;
}
/*
Convention: str[0 : x] = first x chars of str.
dp[a_i][b_i] = True if i[0 : (a_i + b_i)] is an interleaving
of a[0 : a_i] and b[0 : b_i], else False.
*/
bool dp[a.length() + 1][b.length() + 1];
for (int ai = 0; ai <= a.length(); ai++){
for (int bi = 0; bi <= b.length(); bi++){
/*
To dp[a_i][b_i] be true, at least one of the below two should be true:
1) i[0 : (a_i + b_i - 1)] should be an interleaving
of a[0 : (a_i - 1)] and b[0 : b_i]
and a[ai - 1] == i[ai + bi - 1].
2) i[0 : (a_i + b_i - 1)] should be an interleaving
of a[0 : a_i] and b[0 : (b_i - 1)]
and b[bi - 1] == i[ai + bi - 1].
*/
// Keeps track of the above mentioned #1
bool dp_ai_min_1_bi = false;
// Keeps track of the above mentioned #2
bool dp_ai_bi_min_1 = false;
if (ai > 0){
dp_ai_min_1_bi = dp[ai - 1][bi] &&
(a[ai - 1] == i[ai + bi - 1]);
}
if (bi > 0){
dp_ai_bi_min_1 = dp[ai][bi - 1] &&
(b[bi - 1] == i[ai + bi - 1]);
}
// dp[0][0] = Will be true because empty string is an interleaving
// of two empty strings.
dp[ai][bi] = (ai == 0 && bi == 0) ||
dp_ai_min_1_bi ||
dp_ai_bi_min_1;
}
}
return dp[a.length()][b.length()];
}
// -------- END --------
.png)
