Interleaving String [Solved]

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

1. Problem Statement
2. Approach
3. Code
4. Analysis
5. 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;
• 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.