Table of Contents
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;
}