question 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 we include one character from string a or string b and check whether the resultant string formed so far by one particular interleaving of the the current prefix of string a and string b form a prefix of string c this can be achieved using dynamic programming this approach relies on fact that in order to determine whether a substring of string cupto index k can be formed by interleaving strings string a and string b upto indices i and j respectively depends on the characters of string a and string b upto indices i and j only and not on characters coming afterwards complexity analysis time complexity om x n dp array of size n is filled m times where m and n are lengths of string a and string b respectively space complexity on function to check if string c is formed by interleaving of string a and b returns a boolean value check if the length of string c is equal to sum of lengths of string a and b in other words check if string c contains all characters of string a and b create an empty array of length of string b the first value of array dp always holds true driver code function to check if string c is formed by interleaving of string a and b returns a boolean value check if the length of string c is equal to sum of lengths of string a and b in other words check if string c contains all characters of string a and b create an empty array of length of string b the first value of array dp always holds true driver code
def isInterleaving(string_A, string_B, string_C):
    
    
    if(len(string_C) != len(string_A) + len(string_B)): return False
    
    
    dp = [None] * (len(string_B) + 1)
    
    for i in range(len(string_A) + 1):
        for j in range(len(string_B) + 1):
            if(i == 0 and j == 0):
                
                dp[j] = True
            elif(i == 0):
                dp[j] = dp[j - 1] and string_B[j - 1] == string_C[j - 1]
            elif(j == 0):
                dp[j] = dp[j] and string_A[i - 1] == string_C[i - 1]
            else:
                dp[j] = ((dp[j] and string_A[i - 1] == string_C[i + j - 1]) or (dp[j - 1] and string_B[j - 1] == string_C[i + j - 1]))
	
    	
    return dp[len(string_B)]


string_A = input("Enter string A")
string_B = input("Enter string B")
string_C = input("Enter string C")

result = isInterleaving(string_A, string_B, string_C)

if(result):
	print("String C is interleaving String A and String B")
else:
	print("String C is not interleaving String A and String B")