Leetcode 10: Regular Expression Match - dynamic programming

July 6, 2017

Continue to study a DP solution, discussion link is here.
Dynamic programming solution - practice code is here.

Another dynamic programming solution is here. Plan to study the code later. 

Study simple test cases and get more ideas how to design dynamic programming solution, code is here. 

Test cases

1 . test case 1: 

"aa" matches pattern string "a*". a* counts as multiple a. 

2. test case 2:

"a" matches pattern string "a*". a* counts as one a

3. test case 3:

"a" matches pattern string "a*a". a* count as empty

4. test case 4:

"" matches pattern string "a*b*c*". This is the base case. The string is emtpy string. 

Dynamic programming is such a difficult solution to go over with. It is a good idea to write the code which can be memorized and also easy to  reproduce based on a few of basic rules. 

Regular expression matching is a classical algorithm, it is best for the player to train and get some experience how to design a dynamic programming. 

We like to talk about base cases, talk about how many options for a*, zero or 1 or more 3 cases. We like to talk about the matrix starting from (0,0) and to (n,m).

----------------------------------------------------------> left
|
|
V top 


(left-2, top)   (left, top)         (left+1, top)
   

                (left, top+1)       (left+1,top+1)

Plan to spend 20 minutes to study the following notes in the discussion: