regular expression matching:

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

Solution:

被问到这种问题，只能分类讨论。

1. DP
2. 从例子出发，把几种情况都列出来，然后 给他们都写条件。
3. initialization 也比较难。条件为：if p[col] == "*": dp[0][col+1] = dp[0][col - 1]
4. function to next state：
   1. case 1：if s[row] == p[col] or p[col] == ".":
   2. case 2: p[col] == "*":
   3. case 3: all False

class Solution(object):
    def isMatch(self, s, p):

        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        rowNum = len(s)
        colNum = len(p)

        # initialization
        dp = [[False] * (colNum + 1) for i in range(rowNum + 1)]
        dp[0][0] = True
        for col in range(1, colNum):
            if p[col] == "*":
                dp[0][col+1] = dp[0][col - 1]

        # function to next state
        for row in range(rowNum):
            for col in range(colNum):
                if s[row] == p[col] or p[col] == ".":
                    dp[row + 1][col + 1] = dp[row][col]
                elif p[col] == "*":
                    # case for zero occurrence of the letter before "*"
                    dp[row + 1][col + 1] = dp[row + 1][col - 1]
                    # case for one or more occurrence of the letter before "*"
                    if s[row] == p[col - 1] or p[col - 1] == ".":
                        # so we take the previous letter result
                        dp[row + 1][col + 1] = dp[row + 1][col + 1] or dp[row][col + 1] 
                else:
                    dp[row + 1][col + 1] = False

        return dp[-1][-1]