题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

class Solution: def match(self, s, pattern): """ :param s: 输入字符串 :param pattern: 待匹配的正则pattern :return: 是否能匹配 """ def helper(cur_s, cur_pattern): # 两个都为空，匹配成功 if not cur_s and not cur_pattern: return True # 如果cur_s不空而cur_pattern为空，匹配失败 # 注意如果cur_s为空而cur_pattern不空，有可能匹配成功。如'', '.*'匹配成功 if cur_s and not cur_pattern: return False # 如果当前pattern的第二个字符是* if len(cur_pattern) > 1 and cur_pattern[1] == '*': # 如果cur_s不空 if cur_s: # *的前一个字符可以匹配 if cur_s[0] == cur_pattern[0] or cur_pattern[0] == '.': return (helper(cur_s[1:], cur_pattern) # 匹配尽可能多个 or helper(cur_s[1:], cur_pattern[2:]) # 匹配1个 or helper(cur_s, cur_pattern[2:])) # 匹配0个 # *的前一个字符匹配失败，跳过* else: return helper(cur_s, cur_pattern[2:]) # cur_s为空，跳过* else: return helper(cur_s, cur_pattern[2:]) else: # 如果当前pattern的第一个字符就是*，跳过这个* if cur_pattern and cur_pattern[0] == '*': return helper(cur_s, cur_pattern[1:]) # 否则判断cur_s和cur_pattern的第一个字符能否匹配 if cur_s: if cur_s[0] == cur_pattern[0] or cur_pattern[0] == '.': return helper(cur_s[1:], cur_pattern[1:]) else: return False # 如果cur_s为空，但是cur_pattern的前两个字符中没有*，说明不可能匹配 else: return False return helper(s, pattern)