[Algo]: Interwoven Strings
Problem Statement:
You are given three string inputs. The third is a result of interweaving the two string inputs. Interweaving means that the characters of the two inputs string can jumbled in such way that the
Solution:
This problem involves exploring different possibilities of mixing and matching the characters of the input strings. So using recursion, we can explore the each such possibility and derive if there is match till current time, and continue till we have constructed the length of the output string.
There can be lot of recursive call which are repetitive and one way to avoid this is to cache if the current possibility is a success or not. If at some point , we hit on the this possibility we can safely assume that all possibilities going forward would be useless and can be avoided. The intuition to this is not straight forward. But deeper look is needed with specific inputs to derive this.
Lesson learnt:
- Need to identify repeated recursive calls.
- And find a way to store the results of those calls and use it later to avoid redundant calls.
