10. Regular Expression Matching
dp问题是先找到状态，这一步我找出来了，然后要初始化，我没考虑到下面提到的corner case，然后要写出递推公式，我写出了 p[i] != "*"的情况，然后就不会了。。。研究了一个答案，虽然明白了，但是感觉如果再换一种方式来问，我还是不太能答出来这个问题。也没什么其它办法，估计只能多写两遍，增加对这种题型的感觉和熟练度。

class Solution(object):
    def isMatch(self, s, p):
        # The DP table and the string s and p use the same indexes i and j, but
        # table[i][j] means the match status between p[:i] and s[:j], i.e.
        # table[0][0] means the match status of two empty strings, and
        # table[1][1] means the match status of p[0] and s[0]. Therefore, when
        # refering to the i-th and the j-th characters of p and s for updating
        # table[i][j], we use p[i - 1] and s[j - 1].

        # Initialize the table with False. The first row is satisfied.
        table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]

        # Update the corner case of matching two empty strings.
        table[0][0] = True

        # Update the corner case of when s is an empty string but p is not.
        # Since each '*' can eliminate the charter before it, the table is
        # vertically updated by the one before previous. [test_symbol_0]
        # 也就是说对于某一个i也就是p[:i]匹配与空串""等于当p[i-1]是为*，p[:i-2]匹配与空串
        # 例子 p = "a*b*" p[:4] 匹配与""就等于 p[3] == "*" and p[:2]匹配与空串结果为True 
        for i in range(2, len(p) + 1):
            table[i][0] = table[i - 2][0] and p[i - 1] == '*'

        for i in range(1, len(p) + 1):
            for j in range(1, len(s) + 1):
                if p[i - 1] != "*":
                    # Update the table by referring the diagonal element.
                    # 这个好理解，如果当前p值不为*，那么当前的值就等于之前的值and一些当前条件
                    table[i][j] = table[i - 1][j - 1] and (p[i - 1] == s[j - 1] or p[i - 1] == '.')
                else:
                    # 当此时的字符为*时候，则分为两种情况
                    # Eliminations (referring to the vertical element)
                    # Either refer to the one before previous or the previous.
                    # I.e. * eliminate the previous or count the previous.
                    # [test_symbol_1]
                    # 第一种情况是*代表之前的0个字符，或者代表之前的1个字符
                    # 也就是看看当前的s[:j]是否匹配与 p[:i-1]或者p[:i-2]
                    table[i][j] = table[i - 2][j] or table[i - 1][j]
                    
                    # Propagations (referring to the horizontal element)
                    # If p's previous one is equal to the current s, with
                    # helps of *, the status can be propagated from the left.
                    # [test_symbol_2]
                    # 第二种情况*是扩充了当前的字符
                    # 也就是说如果s[j-1]也就是当前考虑的字符和p[i-2]也就是*之前的字符相同
                    # 或者p[i-2]也就是*之前的字符为"."那么可以用当前的匹配 or p[:i] 和 s[:j-1]的匹配
                    # 例如 p = "ab*" s = "abbbb"
                    # p[:3] 和 s[:4] 也就是abbb匹配时，因为p[2] = "*" p[1] == s[3]
                    # 所以 p[:3]和s[:4]的匹配就相当于 or 上 p[:3]和s[:3]的匹配，因为后一位可以由*扩展而来
                    if p[i - 2] == s[j - 1] or p[i - 2] == '.':
                        table[i][j] |= table[i][j - 1]

        return table[-1][-1]