Check whether a given string is an interleaving of two other given strings

Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. 
C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.

Solution:
Pick each character of C one by one and match it with the first character in A. If it doesn’t match then match it with first character of B. If it doesn’t even match first character of B, then return false. If the character matches with first character of A, then repeat the above process from second character of C, second character of A and first character of B. If first character of C matches with the first character of B (and doesn’t match the first character of A), then repeat the above process from the second character of C, first character of A and second character of B. If all characters of C match either with a character of A or a character of B and length of C is sum of lengths of A and B, then C is an interleaving A and B.

// C/C++ program to check if given string is an interleaving
// of the other two strings
#include<stdio.h>
// Returns true if C is an interleaving of A and B,
// otherwise returns false
bool isInterleaved (char *A, char *B, char *C)
{
    // Iterate through all characters of C.
    while (*C != 0)
    {
        // Match first character of C with first character
        // of A. If matches them move A to next
        if (*A == *C)
            A++;
        // Else Match first character of C with first
        // character of B. If matches them move B to next
        else if (*B == *C)
            B++;
 
        // If doesn't match with either A or B, then return
        // false
        else
            return false;
        
        // Move C to next for next iteration
        C++;
    }
    // If A or B still have some characters, then length of
    // C  is smaller than sum of lengths of A and B, so
    // return false
    if (*A || *B)
        return false;
    return true;
}
// Driver program to test above functions
int main()
{
    char *A = "AB";
    char *B = "CD";
    char *C = "ACBG";
    if (isInterleaved(A, B, C) == true)
        printf("%s is interleaved of %s and %s", C, A, B);
    else
        printf("%s is not interleaved of %s and %s", C, A, B);
    return 0;
}

Output:

  ACBG is not interleaved of AB and CD

Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.

Note that the above approach doesn’t work if A and B have some characters in common. For example, if string A = “AAB”, string B = “AAC” and string C = “AACAAB”, then the above method will return false.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar