Get this book -> Problems on Array: For Interviews and Competitive Programming

The *Interleaving Strings* is a classical dynamic programming problem that involves whether a string can be formed by interleaving two strings. In this article, we'll explore this problem in depth and provide a C++ implementation using dynamic programming.

## Table of Contents

- Problem Statement
- Approach
- Code
- Analysis
- Applications

### Problem Statement

Given three strings A, B, and C, determine whether C is an interleaving of A and B. An interleaving of two strings maintains the relative order of the characters from each string, but allows for those characters to be interleaved with each other.

- Example : Consider the strings A = "abc" and B = "def". The string C = "adbecf" is an interleaving of A and B because it maintains the relative order of the characters from each string, but interleaves them with each other. However, the string C = "aebdcf" is not an interleaving of A and B because it violates the relative order of the characters from each string.

### Approach

- The idea is to use a two-dimensional array
*dp[i][j]*to represent whether the first*i+j*characters of the interleaved string C, can be formed by interleaving the first*i*characters of the first string A ,and the first*j*characters of the second string B. - To fill the
*dp*array, we need to come up with a recurrence relation based on the previous values of array. For this problem, at each step we have two possible ways to add a character to the interleaved string, either by taking a character from the first string or from the second string. - Based on this observation, the dp state can be defined as follows :
*dp[i][j]*is*true*if and only if the first*i+j*characters of the interleaved string can be formed by interleaving the first*i*characters of the first string and the first*j*characters of the second string. - i.e.,
- If
*A[i-1]*(0 based idx) matches*C[i+j-1]*, then*dp[i][j]*is true if and only if*dp[i-1][j]*is true. - If
*B[j-1]*(0 based idx) matches*C[i+j-1]*, then*dp[i][j]*is true if and only if*dp[i][j-1]*is true. - Otherwise,
*dp[i][j]*is false;

- If
- We can start with the base case that
*dp[0][0] = 0*as empty string can be formed by interleaving two empty strings. - Using this recurrence relation, we can fill the dp table bottom-up starting with dp[0][0]. At the end the answer to the problem is
*dp[m][n]*, where m is size of string A and n is size of string B.

### Code

**Iterative Version**

```
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isInterleave(string s1, string s2, string s3) {
int m = s1.length();
int n = s2.length();
int sz = s3.length();
if (sz != m + n) return false;
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (!i && !j) continue;
if (i > 0 && s1[i-1] == s3[i+j-1]) {
dp[i][j] = dp[i-1][j];
}
if (j > 0 && s2[j-1] == s3[i+j-1]) {
dp[i][j] = dp[i][j] || dp[i][j-1];
}
}
}
return dp[m][n];
}
int main() {
string s1 = "aabcc";
string s2 = "dbbca";
string s3 = "aadbbcbcac";
cout << isInterleave(s1, s2, s3) << endl;
return 0;
}
```

**Recursive Version**

```
#include <iostream>
#include <string>
using namespace std;
bool dp(string s1, string s2, string s3, int i, int j, int k) {
if (k == s3.length()) {
return i == s1.length() && j == s2.length();
}
bool match1 = i < s1.length() && s1[i] == s3[k];
bool match2 = j < s2.length() && s2[j] == s3[k];
if (match1 && match2) {
return dp(s1, s2, s3, i+1, j, k+1) || dp(s1, s2, s3, i, j+1, k+1);
} else if (match1) {
return dp(s1, s2, s3, i+1, j, k+1);
} else if (match2) {
return dp(s1, s2, s3, i, j+1, k+1);
}
return false;
}
bool isInterleave(string s1, string s2, string s3) {
return dp(s1, s2, s3, 0, 0, 0);
}
int main() {
string s1 = "aabcc";
string s2 = "dbbca";
string s3 = "aadbbcbcac";
cout << isInterleave(s1, s2, s3) << endl;
return 0;
}
```

### Analysis

**Time Complexity**:

The Time Complexity of this algorithm is **O(nm)**, where m and n are length of input strings A and B. This is because we need to fill the dp array of size (m+1)*(n+1) by considering all possible character combinations from the two input stings.

**Space Complexity**

The Space Complexity is also **O(nm)** as we need to store the dp array which is of size nm.

### Applications

Similar idea is used in bioinformatics to find whether two DNA sequences can be merged into a single DNA sequence, also in image processing, the problem of merging two images into a single image and many other. Overall, the interleaving string problem is a useful and versatile problem that can be solved using dynamic programming.