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

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
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:
Related Problems:
This problem generally requires more thinking than the problems we have seen so far in 2Strings DP series. The purpose of including this problem in our series is to show how we could use the Template discussed in 2Strings DP chapter to solve nontrivial problems. I would highly encourage you to go through the chapter on 2Strings DP Fundamentals and have a strong grasp on the template discussed.
I have put the explanation of the algorithm we would implement in the inline comment in the code itself. We would be using Bottomup tabulation approach and would solve in the increasing order of length for strings so that when we solve for the higher length order for the strings we could use the already computed results for lower lengths of the strings (optimal substructures).
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Space Optimization:
We can do further optimization by solving this problem by using 1D array instead of 2D array. I have discussed the algorithm in the inline comment in the code.
Java Code:
Login to Access Content
Python Code:
Please subscribe to access the code.
After subscribing please come back and refresh this page.