正则表达式匹配

Python

class Solution(object):
    def isMatch(self, s, p):
        len_s = len(s)
        len_p = len(p)
        res_m = [[False for j in range(len_p + 1)] for i in range(len_s + 1)]
        for i in range(len_s + 1):
            res_m[i][0] = False
        res_m[0][0] = True
        if len_p != 0:
            res_m[0][1] = False
        for j in range(2, len_p + 1):
            if p[j-1] == '*':
                res_m[0][j] = res_m[0][j-2]
            else:
                res_m[0][j] = False
        for i in range(1, len_s + 1):
            for j in range(1, len_p + 1):
                if p[j-1] != '*':
                    if p[j-1] == s[i-1] or p[j-1] == '.':
                        res_m[i][j] = res_m[i-1][j-1]
                    else:
                        res_m[i][j] = False
                else:
                    if p[j-2] == s[i-1] or p[j-2] == '.':
                        res_m[i][j] = res_m[i][j -
                                               1] or res_m[i][j-2] or res_m[i-1][j]
                    else:
                        res_m[i][j] = res_m[i][j-2]
        return res_m[len_s][len_p]