10. Regular Expression Matching
dp問題是先找到狀態(tài)，這一步我找出來了，然后要初始化，我沒考慮到下面提到的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]匹配與空串""等于當(dāng)p[i-1]是為*，p[:i-2]匹配與空串
        # 例子 p = "a*b*" p[:4] 匹配與""就等于 p[3] == "*" and p[:2]匹配與空串結(jié)果為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.
                    # 這個好理解，如果當(dāng)前p值不為*，那么當(dāng)前的值就等于之前的值and一些當(dāng)前條件
                    table[i][j] = table[i - 1][j - 1] and (p[i - 1] == s[j - 1] or p[i - 1] == '.')
                else:
                    # 當(dāng)此時的字符為*時候，則分為兩種情況
                    # 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個字符
                    # 也就是看看當(dāng)前的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]
                    # 第二種情況*是擴充了當(dāng)前的字符
                    # 也就是說如果s[j-1]也就是當(dāng)前考慮的字符和p[i-2]也就是*之前的字符相同
                    # 或者p[i-2]也就是*之前的字符為"."那么可以用當(dāng)前的匹配 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]的匹配就相當(dāng)于 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]