Regular Expression Matching

正则表达式匹配，这道题和通配符那道也非常类似，但是还是有区别，受苦了两个钟头才做出来... 主要还是星号的匹配问题非常多，再加上一些boundary case没有通配符那道好处理，花了很多时间，首先总体来讲，这道题的点号和通配符的问号一样没有任何需要特殊处理的地方，但是星号的逻辑则变复杂了，首先是dp矩阵的初始化就比较麻烦，左边缘还是全False，但是到上边缘，因为星号在这道题里必须基于前面的字符串匹配而不是自己本身就能匹配，且星号在这道题里面只能匹配一个对应的字符任意次而不是，这里稍微先对统配符那道简单了一点，但是又导致在检查星号的情况时，必须要考虑星号前面的那个p字符与当前s字符的匹配情况

矩阵初始化方面，上边缘的初始化有几种情况需要注意，一是光有一个星号不代表可以直接找dp[i][j-2]了，而应该要先判断当前p字符的前一个字符是否非法，也就是有两个星号连在一起，这种情况直接返回false不需要DP了

for i in xrange(1, m + 1):
    if p[i - 1] == '*':
        if p[i - 2] == '*':
            return False
        dp[0][i] = dp[0][i - 2]
    else:
        dp[0][i] = False

下面是最麻烦的状态转移，还是星号的问题，这里星号一样有三种情况

• 星号不匹配，则找dp[i][j - 2]
• 星号匹配一次，则找dp[i][j - 1]
• 星号匹配多次，则找dp[i - 1][j]的同时，还要检查s[i]是否等于p[j - 1]，因为这两个字符不相等的话匹配无从谈起，另外还有p[j-1]是有可能等于点号的

基于上面三种情况，代码如下

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        n = len(s)
        m = len(p)

        dp = [([False] * (m + 1)) for _ in xrange(n + 1)]
        dp[0][0] = True

        for i in xrange(1, m + 1):
            if p[i - 1] == '*':
                if p[i - 2] == '*':
                    return False
                dp[0][i] = dp[0][i - 2]
            else:
                dp[0][i] = False

        # 星号判断的那一行逻辑偏复杂

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = (dp[i][j - 2] or (dp[i][j - 1]) or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')))

        return dp[n][m]