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

代码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

然后就在aaa，a*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