• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.






Python Code:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:



Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave