10。正则表达式匹配题目来源：https://leetcode-cn.com/problems/regular-expression-matching题目给你一个字符串s和一个字符模式p，请实现一个支持'.'的正则表达式匹配。和'*'。'.'匹配任意单个字符'*'匹配前一个元素的零个或多个所谓匹配就是覆盖整个字符串s，而不是字符串的一部分。注意：s可能为空，只包含a-z中的小写字母。p可以为空，只包含小写字母a-z和字符.和*。示例1：输入：s="aa"p="a"输出：false解释：“a”无法匹配整个字符串“aa”。示例2：输入：s="aa"p="a*"输出：true解释：因为'*'表示它可以匹配零个或多个前一个元素，这里前一个元素是'a'。因此，字符串“aa”可以被认为是“a”重复了一次。示例3：输入：s="ab"p=".*"输出：true解释：".*"表示可以匹配零个或多个（'*'）任意字符（'.'）。示例4：输入：s="aab"p="c*a*b"输出：true解释：因为'*'表示零个或多个，所以这里'c'为0，'a'重复一次。所以可以匹配到字符串“aab”。示例5：输入：s="mississippi"p="mis*is*p*."Output:false解题思路暴力解先从【暴力解】的角度把问题说清楚。在本题中，难点在于处理这两个符号。和*。如果它只是要求检查两个正常字符是否匹配。然后通过直接遍历，检查每个数组对应的元素是否相同，判断是否匹配。例如：defisMatch(s,p):iflen(s)!=len(p):returnFalseforiinrange(p):ifs[i]!=p[i]:returnFalsereturnTruethat代码大概就是这样。然后我们写成递归的形式，下面是伪代码：defisMatch(s,p):"""s:textp:pattern"""ifpisempty:returnsisemptyfirst_match=(snotempty)andp[0]==s[0]returnfirst_matchandisMatch(s[1:],p[1:])上面代码中其实是判断前面的元素是否匹配，然后逐层判断后面的是否匹配元素也匹配，从而找到答案。现在让我们处理两个符号的问题，符号。表示匹配时除换行符以外的任何字符（这里不做解释，想了解的可以直接上网搜索）。理解了这个符号的含义之后，这里所能表达的意思也会随之发生变化，也就是说，当符号。出现在p中，不管s对应的元素是什么字符（题目说s只包含a-z字符）都可以匹配，现在按照上面的伪代码修改：defisMatch(s,p):"""s:textp:pattern"""ifnotp:returnnotsfirst_match=bool(s)andp[0]in{s[0],'.'}返回first_matchandisMatch(s[1:],p[1:])这里唯一不同的是first_match的判断，因为p中的元素可能有固定的字符，或者.符号，因此当p中的字符与s中的相应字符相同时，或者p是a。这里的字符，它们都可以匹配。所以现在往下看*符号，它的意思是重复零次或多次。所以这里最明显的性格就是重复多少次的问题？这里考虑用递归的方式写，假设重复n次。其实这里不用考虑n的个数，这个交给递归实现。考虑到现在的情况，这里应该只有两种选择，要么匹配0次，要么匹配1次。那么相应的代码应该修改为（这里是找到*的情况）：#这意味着当找到`*`时，如果len(p)>=2andp[1]=='*':#Here需要考虑匹配0次的问题，比如aa,c*aa#还要考虑匹配多次的问题，比如aa,a*returnisMatch(s,p[2:])orfirst_matchandisMatch(s[1:],p)这段代码中isMatch(s,p[2:])表示字符匹配0次，跳过p中字符与*组合的部分。后者的意思是p[0]和s[0]匹配后，继续判断s的下一个元素。其中p被保留，只有s向后移动，以实现*匹配多次的功能。从这一点来看，其实可以说是可以说清楚这两个符号的具体实现。完整代码请参见【代码实现】部分。动态规划思想：在上述暴力求解方法中，动态规划频繁使用切片操作，复杂度高。这里在暴力破解的基础上，采用动态规划的方法定义变量i和j记录当前匹配到的位置，用dp(i,j)表示s[i:]和p[j:]可以匹配。,避免频繁切片。这里也引入备忘录的概念，避免重复计算。具体代码请参考【代码实现】部分。代号实现暴力解|代码实现classSolution:defisMatch(self,s:str,p:str)->bool:ifnotp:returnnotsfirst_match=bool(s)andp[0]in{s[0],'.'}如果len(p)>=2andp[1]=="*":returnself.isMatch(s,p[2:])orfirst_matchandself.isMatch(s[1:],p)else:returnfirst_match和self.isMatch(s[1:],p[1:])动态规划|代码实现classSolution:defisMatch(self,s:str,p:str)->bool:memo={}defdp(i,j):if(i,j)notinmemo:ifj==len(p):returni==len(s)else:first_match=i
