【LeetCode】0010 正则表达式匹配

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

代码：

# -*- coding:utf-8 -*-
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) <= 0:
            return len(s) <= 0
        match = len(s) > 0 and (s[0] == p[0] or p[0] == '.')
        if len(p) > 1 and p[1] == '*':
            # 对应*是无用的（也就是0次）   和    *是有用的
            return self.isMatch(s, p[2:]) or (match and self.isMatch(s[1:], p))
        else:
            return match and self.isMatch(s[1:], p[1:])


if __name__ == '__main__':
    s = 'aaa'
    p = 'ab*a*c*a'
    s = 'mississippi'
    p = 'mis*is*p*.'
    print(Solution().isMatch(s, p))

思路：这道题比较明显的是用动态规划做，但是我一直没找到合适的状态空间，试了几种方法，匹配倒是可以匹配，但是对于一些比如s匹配完p还有未匹配的一些特殊情况没办法处理，所以选择了递归处理，这个就是简单的每次只处理1（2）位，然后向下递归直至字符串长度为0。

思考：查了查网上的资料，发现了动归一直解决不了的问题所在，我在匹配的时候weight列表用的是整数，也就是当前匹配长度，显然这种解决方案在这道题里是不合适的，因为一旦某一个不匹配所有的都不匹配，所以应该用True或者Flase。