10. Regular Expression Matching

递归匹配字符串，可以精简代码。据说可以用 dp 实现

class Solution:

    # a-z . A-Z &
    def recursion(self, s, si, p, pi):
        if len(s) == si and len(p) == pi:
            return True
        elif len(p) == pi:
            return False
        elif p[pi] >= 'a' and p[pi] <= 'z':
            if si < len(s) and s[si] == p[pi]:
                return self.recursion(s, si + 1, p, pi + 1)
            else:
                return False
        elif p[pi] == '.':
            return self.recursion(s, si + 1, p, pi + 1)
        elif p[pi] >= 'A' and p[pi] <= 'Z':
            result = self.recursion(s, si, p, pi + 1)
            if result:
                return True
            while si < len(s):
                if p[pi].lower() == s[si]:
                    si += 1
                    result = self.recursion(s, si, p, pi + 1)
                    if result:
                        return True
                else:
                    break
        elif p[pi] == '&':
            result = self.recursion(s, si, p, pi + 1)
            if result:
                return True
            while si < len(s):
                si += 1
                result = self.recursion(s, si, p, pi + 1)
                if result:
                    return True
                
        return False

    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        pr = p[::-1]
        pc = ""
        i = 0
        last = ''
        isAppend = True
        while i < len(pr):
            isAppend = True
            pp = pr[i]
            if pp >= 'a' and pp <= 'z':
                last = pp
            elif pp == '.':
                last = pp
            elif pp == '*':
                i += 1
                pp = pr[i] 
                if pp >= 'a' and pp <= 'z':
                    last = pp.upper()
                else:
                    last = '&'
            
            pc += last         
            i += 1
        
        # print(s)
        # print(p)
        p = pc[::-1]
        # print(p)

        result = self.recursion(s, 0, p, 0)
        print(result)
        return result

测试用例

import Solution

s = Solution.Solution()

s.isMatch("ab", ".*c") # False
s.isMatch("aa", "a") # False
s.isMatch("aa", "a*") 
s.isMatch("ab", ".*")
s.isMatch("aab", "c*a*b")
s.isMatch("mississippi", "mis*is*p*.") # False
s.isMatch("abaaac", ".*a*a*aa.c")
s.isMatch("aa", "a*")
s.isMatch("", "a*")