I tried solving Leetcode problem #10( Regular Expression Matching) for fun, ended up spending hours on it.
problem Link: https://leetcode.com/problems/regular-expression-matching/description/
I took a naive greedy string construction approach to check if the string s matched the pattern p.
That worked for simple cases where: p="a*b" s="aaab" output:True
But failed in cases where p ="ab*a*c*a" and s ="aaa", output should be True
why greedy string construction failed:
the flaw was that a* is not a single choice, it can match "", "a", "aa", "aaa" etc.
To determine if the pattern p matches s, all possibilities of a* must be explored while exploring the rest of the characters. Brute forcing this will result in exponential time complexity.
So after ELEVEN failed attempts, I finally gave up and searched for the solution. That is where I came across DP top-down approach (recursive memoization).
The idea of Dynamic programming is to break down complex problem into small sub-problems, saving and reusing the overlapping results.
After learning the full theory, it took me a couple more tries to come even remotely close to solving it.
Even after taking a look at the solution code, I still made some mistakes when I tried replicating it without looking.
But either way, this whole process made me really happy, and reminded me of why I loved programming in the first place: Solving problems beautifully.
P.S. Dynamic programming can be used for bunch of optimization problems including Schedule Optimization, Knapsack, Combinatorial problems, path finding on grids and many more.
I am hoping to use it for a schedule optimization project that I created a long time ago.
