Home » Technical Interview Questions » String Interview Questions » Given string is interleaving of two other strings or not

Given string is interleaving of two other strings or not



String

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

READ  Arrange given numbers to form the biggest number

 

 

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup