Check whether a given string is an interleaving of two other given strings
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
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 2-Strings DP series. The purpose of including this problem in our series is to show how we could use the Template discussed in 2-Strings DP chapter to solve non-trivial problems. I would highly encourage you to go through the chapter on 2-Strings 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 Bottom-up 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 sub-structures).
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.
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
