题目描述
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
思路
从后往前比较，递归判断，判断条件太多。无法AC
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
s = '^' + s
pattern = '^' + pattern
i = len(s) - 1
j = len(pattern) - 1
star_match = False
while i>=0 and j>=0:
if star_match:
if pattern[j] == '.' or pattern[j] == s[i]:
if self.match(s[1:i], pattern[1:j]): # 先靠前匹配，从1开始是去掉index为0的^
return True
else:
i -= 1
else:
j -= 1
star_match = False
else:
if s[i] == pattern[j] or pattern[j] == '.':
i -= 1
j -= 1
elif pattern[j] == '*':
star_match = True
j -= 1
else:
return False
return (i == -1 and j == -1)
print(Solution().match('aa', 'a*'))