[刷题]LeetCode 10. 正则表达式匹配

发布于 2021-10-10  2 次阅读


代码git:History for 10. 正则表达式匹配.py - WankkoRee/LeetCodeAnswersWithPython3

这题刚开始感觉挺难的,直觉告诉我用递归+回溯应该能出。

刚开始的大致思路是两个字符串一起遍历,然后优先判断第二位是不是*,是的话就判断第一位是不是相等或者正则第一位是.,不是的话那就应该是当作空字符处理,直接正则字符串往后跳2位。然后如果不是*的话,那就正常匹配第一位是不是相等或者正则第一位是.,如果不是的话那就说明不匹配。

至于递归的边界条件的话,两个字符串都空肯定是匹配了的,如果文本字符串空了但是正则字符串没空的话,就要考虑是不是还有*可以当空字符匹配,否则的话就不匹配。

所以大致可以写个如下的脚本。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n1 = len(s)
        n2 = len(p)
        if n1 == 0 and n2 == 0:
            return True
        elif n1 == 0 and n2 % 2 == 0 and p[1] == '*':
            return self.isMatch(s, p[2:])
        elif n1 == 0 or n2 == 0:
            return False
        if n2 >= 2 and p[1] == '*':
            if p[0] == '.':
                return self.isMatch(s[1:], p)
            elif p[0] == s[0]:
                return self.isMatch(s[1:], p)
            else:
                return self.isMatch(s, p[2:])
        elif p[0] == '.':
            return self.isMatch(s[1:], p[1:])
        elif p[0] == s[0]:
            return self.isMatch(s[1:], p[1:])
        else:
            return False

solution = Solution()
assert solution.isMatch("aa", "a") == False
assert solution.isMatch("aa", "a*") == True
assert solution.isMatch("ab", ".*") == True
assert solution.isMatch("aab", "c*a*b") == True
assert solution.isMatch("mississippi", "mis*is*p*.") == False

然后就在aaaa*a这个数据上碰壁了,因为我脚本的思路会在a*上直接把aaa匹配完导致最后正则那边还剩个a没东西匹配。

所以确实是要用到回溯了,有些不合理的*需要靠回溯给跳过匹配,所以改改脚本。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # print(s, p)
        n1 = len(s)
        n2 = len(p)
        if n1 == 0 and n2 == 0:
            return True
        elif n2 >= 2 and p[1] == '*':
            if n1 == 0:
                return self.isMatch(s, p[2:])
            else:
                if p[0] == '.' or p[0] == s[0]:
                    b = self.isMatch(s[1:], p)
                    if b:
                        return True
                    else:
                        return self.isMatch(s, p[2:])
                else:
                    return self.isMatch(s, p[2:])
        elif n1 == 0 or n2 == 0:
            return False
        elif p[0] == '.' or p[0] == s[0]:
            return self.isMatch(s[1:], p[1:])
        else:
            return False

solution = Solution()
assert solution.isMatch("aa", "a") == False
assert solution.isMatch("aa", "a*") == True
assert solution.isMatch("ab", ".*") == True
assert solution.isMatch("aab", "c*a*b") == True
assert solution.isMatch("mississippi", "mis*is*p*.") == False

assert solution.isMatch("aaa", "a*a") == True

过是过了,但是用时挺长的,这个应该就是递归的正常水平了,要短耗时的话就得上dp了。挖个坑后面回来写个dp解法看看。

执行用时: 1000 ms , 在所有 Python3 提交中击败了 5.18% 的用户
内存消耗: 15.1 MB , 在所有 Python3 提交中击败了 56.76% 的用户
通过测试用例: 353 / 353


The End


什么都会,但又什么都不会。