leetcode hard 10. 正则表达式匹配

https://leetcode-cn.com/problems/regular-expression-matching/

思路:动态规划

dp：(len(s) +1)* (len(p) + 1)
dp[ii][jj]代表s[0,i-1]和p[0,j-1]是否匹配，故有ii=i+1,jj=j+1。也就是说i,j对应比较时候改变的是dp[i+1][j+1]时的位置。
边界情况,s='',需要先把第一行初始化，这时候就是下面的特殊情况，即当p[j]=='*'时，s[i]!=p[j-1]，dp[ii][jj] = dp[ii][jj-2]。
先分两类：

s[i]==p[j]，(或p[j]=='.')dp[ii][jj] = dp[ii-1][jj-1]，当前两个字符相等，只需要各退一步看是否相等。
s[i]==p[j],p[j]=='*',再分两大类。为了简便，设置Sx，Pzy，y='*'。
s[i]!=p[j-1],即x!=z，则Sx必须和P匹配，dp[ii][jj] = dp[ii][jj-2]
s[i]==p[j-1],即x==z，分几种匹配情况。
Sx和P匹配，x和z*匹配，dp[ii][jj] = dp[ii][jj-2]
Sx和Pz匹配，''和*匹配，dp[ii][jj] = dp[ii][jj-1]
S和P匹配，x和z*匹配，dp[ii][jj] = dp[ii-1][jj-2]
S和Pz匹配，x和*匹配，dp[ii][jj] = dp[ii-1][jj-1]
S和Pz*匹配，x和*匹配，dp[ii][jj] = dp[ii-1][jj]

代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(s) == 0 and len(p) == 0: return True
        dp = []
        for i in range(len(s) + 1):
            dp.append([0] * (len(p) + 1))
        dp[0][0] = 1

        for j in range(len(p)):
            ii, jj = 0, j + 1
            if p[j] == '*':
                if j > 0:
                    dp[ii][jj] = dp[ii][jj - 2]
        for i in range(len(s)):
            for j in range(len(p)):
                ii, jj = i + 1, j + 1
                if s[i] == p[j] or p[j] == '.':
                    dp[ii][jj] = dp[ii - 1][jj - 1]
                else:
                    if p[j] == '*':
                        if j > 0 and (s[i] == p[j - 1] or p[j - 1] == '.'):
                            dp[ii][jj] = max(dp[ii - 1][jj], dp[ii - 1][jj - 1], dp[ii - 1][jj - 2], dp[ii][jj - 2],
                                             dp[ii][jj - 1])
                        elif j > 0 and s[i] != p[j - 1] and p[j - 1] != '.':
                            dp[ii][jj] = dp[ii][jj - 2]

        return dp[-1][-1] == 1