【leetcode】正则表达式匹配【python】【递归，后序遍历】

落日映苍穹つ 2022-05-09 11:06 113阅读 0赞

[题目地址][Link 1]  
![在这里插入图片描述][70]

class Solution(object):
        def myMatch(self, s, p, s_index, p_index):
            print(s_index, p_index)
            if p == '' and s != '':
                #print(1)
                return False
            if s == '':
                if p == '' or (len(p) >=2 and p[1] == '*'):
                    return True
                else:
                    print(2)
                    return False
            if p_index == -1:
                if s_index == -1:
                    return True
                else:
                    print(3)
                    return False
            if s_index == -1:
                if p_index == 0:
                    if s[0] != p[0]:
                        print(4)
                        return False
                    # elif s[0] == p[0]:
                    # return True
                else:
                    return self.myMatch(s, p, s_index, p_index - 2)
            if p[p_index] == '*':
                if s_index > -1 and (p[p_index - 1] == '.' or (s[s_index] == p[p_index - 1] and s[s_index - 1] != p[p_index - 2] and p[p_index - 2] != '*')):
                    return self.myMatch(s, p, s_index - 1, p_index)
                else:
                    return self.myMatch(s, p, s_index, p_index - 2)
            else:
                if p[p_index] == '.' or p[p_index] == s[s_index]:
                    return self.myMatch(s, p, s_index - 1, p_index - 1)
                else:
                    print(5)
                    return False
    
    
        def isMatch(self, s, p):
            """ :type s: str :type p: str :rtype: bool """
            return self.myMatch(s, p, len(s) - 1, len(p) - 1)
    
    sol = Solution()
    print(sol.isMatch('aaa', 'ab*a*c*a'))

**这样无法识别’aaa’ 与 ‘ab*a*c*a*’这种，因为无法识别出，到底遇到\*的时候，移动几个字母**  
改进版

class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            # 判断匹配规则是否为空
            if p == "":
                # p为空的时候，判断s是否为空，则知道返回True 或 False
                return s == ""
            # 判断匹配规则是否只有一个
            if len(p) == 1:
                # 判断匹配字符串长度是否为1，和两者的第一个元素是否相同，或匹配规则使用.
                return len(s) == 1 and (s[0] == p[0] or p[0] == '.')
            # 匹配规则的第二个字符串不为*，当匹配字符串不为空的时候
            # 返回 两者的第一个元素是否相同，或匹配规则使用. and 递归新的字符串(去掉第一个字符的匹配字符串 和 去掉第一个字符的匹配规则)
            if p[1] != "*":
                if s == "":
                    return False
                return (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:], p[1:])
            # 当匹配字符串不为空 and (两者的第一个元素是否相同 or 匹配规则使用.)
            while s and (s[0] == p[0] or p[0] == '.'):
                # 到了while循环，说明p[1]为*，所以递归调用匹配s和p[2:](*号之后的匹配规则)
                # 用于跳出函数，当s循环到和*不匹配的时候，则开始去匹配p[2:]之后的规则
                if self.isMatch(s, p[2:]):
                    return True
                # 当匹配字符串和匹配规则*都能匹配的时候，去掉第一个字符成为新的匹配字符串，循环
                s = s[1:]
            # 假如第一个字符和匹配规则不匹配，则去判断之后的是否匹配
            return self.isMatch(s, p[2:])

[Link 1]: https://leetcode-cn.com/problems/regular-expression-matching/description/
[70]: /images/20220509/bc6241b046914f47b66ad778dd5e4452.png