DP — Regular Expression Matching

solve(s, p) — implement matching of the whole string s against the pattern
p, which supports two special characters:

• . matches any single character.
• * matches zero or more of the preceding element (so a* matches "",

"a", "aa", ...). The pattern never starts with * and every * follows a
valid element.

Let dp[i][j] be true when the first i characters of s match the first j
characters of p. A * can either drop its element (dp[i][j-2]) or consume one
more character of s when the element matches (dp[i-1][j]).

Examples

solve("aa", "a")                    → false
solve("aa", "a*")                   → true
solve("ab", ".*")                   → true
solve("aab", "c*a*b")               → true
solve("mississippi", "mis*is*p*.")  → false
solve("", "a*")                     → true