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