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.



Copyright (c) 2019-2022, Algotree.org.
All rights reserved.