正则表达式匹配

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true

leetcode第十题，拿C++写的时候发现初始化数组如果只写一个值是不行的，其他元素的内存是脏的，需要写成 {} 方能初始化为默认值。

这道题用的是动态编程，确认最优子结构即可，topdown或者 bottomup都可以。

两个字符串 s 和 p，子问题就是是否子字符串也匹配，注意，s[0]可以不和p[0]匹配。粗略看，假设s长度为lenS，p长度为lenP，那么算法的时间复杂度应该是O(lenS*lenT) - O(n**2)。

todo：自定向下的方法，自底向上的方法，纯递归就不写了。

设置一个表 memo[lenS+1][lenP+1] 来记录子字符串s[i:lenS]，其中 i in range(0, lenS)。

设空字符串与空字符串默认匹配，即s[lenS:]与 p[lenP:] 是匹配的，作为哨兵。