Given string is interleaving of two other strings or not


StringViews 1617

Write a function to find if a given string C is interleaving of other two given strings A and B.

Interleaving : C is said to be interleaving of A and B, if it contains all characters of A and B, order of all characters in individual strings (A, B) is preserved.

Examples

a) Input strings :

A : ACBD
B : AB
C : CD

Output : True

b) Input strings:

A : ADBC
B : AB
C : CD

Output : False, even though all characters are there, order is changed.

Time complexity : O(m+n), m and n are lengths of strings.

Algorithm

Given strings be A, B and C, Check if C is interleaving of A and B

1. Iterate through all characters of C, pick characters of C one by one.

2. If it doesn’t matches with first character of A and B then return False.

3. If the character matches with first character of A, repeat above process for second character of C. compare with second character of A and first of B.

4. Continue this process till it reaches the last character of A.

5. If all characters matches either with a character of A or character of B and length of C is sum of length of A and length of B.

6. Return True.

C++ Program

#include <bits/stdc++.h>

using namespace std;

 
//Main function to check 
int main()
{
    const char *A = "CBD";
    const char *B = "AGH";
    const char *C = "ACGHBD";
     //For all charcters in C
    while (*C != 0)
    {
        //If charcter is equal to charcter in A
        if (*A == *C)
        {
            A++;//Increment A pointer, next charcter
        }
        //If charcter is equal to charcter in B
        else if (*B == *C)
        {
            B++;//Increment B pointer, next character
        }
        //If charcter is not equal to charcter in A and B   
        else
        {
            cout<<"not an interleaving"<<endl;//return false
        }
        C++;//Increment C pointer, next character
    }
    //After finishing all characters in C
    //Characters still left in A or B, Then return false
    if (*A || *B)
    {
        cout<<"not an interleaving"<<endl;;
    }
    //Else return true
    cout<<"ACGHBD is an interleaving of CBD and AGH"<<endl;
    return 0;
}

Try It

 

 

Translate »