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 and only characters of A and B and order of all characters in individual strings is preserved.

Author - coding wallah

March 08, 2023

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 and only characters of A and B and order of all characters in individual strings is preserved.

Cpp Program Code:

Explanation:

We use dynamic programming to solve the problem. We create a 2D array dp to store the results of subproblems. dp[i][j] is true if the first i characters of string A and the first j characters of string B can form the first i+j characters of string C.

We initialize the first row and first column of the dp array based on whether the corresponding character in A or B matches the corresponding character in C. Then, we fill the rest of the dp array by checking whether the current character in C matches the current character in A or B, and whether the previous characters in A and B can form the previous characters in C.

The result is stored in the bottom-right cell of the dp array. If it is true, then C is interleaved of A and B. Otherwise, it is not interleaved.

Finally, we print the appropriate message based on the result of the function isInterleaved.