String Interleave

Given: 3 strings s1, s2 and s3.
Objective: To find out if the string s3 could be formed using characters from string s1 and s2.

Note : The order of characters taken from s1 and s2 to form string s3 should remain the same.

Example: Consider string s1 ( abc ), string s2 [ bca ] and string s3 “abbcca”
One way : String s3 can be formed as [ ( ab ) [ bc ] ( c ) [ a ] ]
other way : String s3 can be formed as [ ( a ) [ b ] ( b ) [ c ] ( c ) [ a ] ]

Dynamic programming approach

Base Case : An empty s3 can be formed using empty s1 and empty s2.

Consider substring of s1 of length 1 i.e ( a ).
Consider substring of s2 of length 1 i.e [ b ].
Using these substrings we could form a substring of length 2. Thus we try to see if a substring of s3 of length 2 i.e “ab” could be formed using ( a ) and [ b ].

Substring s1
( Row )		 Substring s2
( Column )		 Substring s3
a ( length 1 ) b ( length 1 ) ab ( length 2 )

We try to match the end character of substring s3 i.e b with either the end character of substring s1 or end character of substring s2.
If it does, then we need to check if the previous substring of s3 ( of length 1 ) could also be formed using the end character of either s1 or s2. This could easily be deduced from the dynamic programming table.

String_Interleave

Dynamic Programming : Program to check if the string s3 is an interleave of string s1 and s2. 

#include<iostream>
#include<cstring>

using namespace std;

bool CheckInterleave (string s1, string s2, string s3) {

    bool table[101][101] = {{ false }};
    table[0][0] = true; // an empty s1, s2 can generate empty s3

    if (s1.size() + s2.size() != s3.size())
        return false;

    if (s1.size() == 0) {
        if (s2 == s3)
            return true;
        return false;
    }

    if (s2.size() == 0) {
        if (s1 == s3)
            return true;
        return false;
    }

    for (int r=0; r<=s1.size(); r++) {
        for (int c=0; c<=s2.size(); c++) {
            if (r == 0 and c == 0) {
                table[r][c] = true;
            } else if (r == 0) { // Only look for characters in string s2
                table[r][c] = (table[r][c-1] and (s2.at(c-1) == s3.at(c-1)));
            } else if (c == 0) { // Only look for characters in string s1
                table[r][c] = (table[r-1][c] and (s1.at(r-1) == s3.at(r-1)));
            } else {
                table[r][c] = ((table[r-1][c] and (s1.at(r-1) == s3.at(r+c-1))) or 
                               (table[r][c-1] and (s2.at(c-1) == s3.at(r+c-1))));
            }
        }
    }
    // Table
    cout << "==================================== " << endl;
    for (int r=0; r<=s1.size(); r++) {
        for (int c=0; c<=s2.size(); c++)
            cout << table[r][c] << " ";
        cout << endl;
    }
    cout << "==================================== " << endl;
    return table[s1.size()][s2.size()];
}

int main() {

    string s1("abc");
    string s2("bca");
    string s3("abbcca");

    if (CheckInterleave (s1, s2, s3))
        cout << "Yes. [" << s1  << "]" << " interleaved with [" << s2 << "] froms [" << s3 << "]" << endl;
    else
        cout << "No. [" << s1  << "]" << " interleaved with [" << s2 << "] does not form [" << s3 << "]." << endl;

    return 0;
}

Output

==================================== 
1 0 0 0 
1 1 0 0 
1 1 1 0 
0 1 1 1 
==================================== 
Yes. [abc] interleaved with [bca] froms [abbcca]

Time complexity: O ( m⋅n ), where m is the length of string s1 and n is the length of string s2.
Space complexity: O ( m⋅n ), where m is the length of string s1 and n is the length of string s2.

© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"Without requirements or design, programming is the art of adding bugs to an empty text file. - Louis Srygley"