文章目录

一、题目二、注意事项三、思路四、代码总结

---

一、题目

给你一个字符串 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*." 输出: false

二、注意事项

”.*“可匹配任意长度字符串连续偶数个”*“字符代表0个前面的字符，连续奇数个“*”与1个“*”相同。

三、思路

1. 递归

拿到题目首先想到的办法，大概的思路如图，递归计算方向是从右向左，主要是各种情况的考虑。（图中s-1=s.substr(1)) （s的后缀子串包括空字符串）

s=”aedcbbbe“ , p=“a.*a**b*..” 的匹配过程

2. 动态规划

看了题解之后发现用动态规划方法，从左往右逐步计算更加科学，精简表达式还可以很好合并一些特殊情况。

当p[j]！=*的时候，只需匹配当前两个字符，成功则为1，不成功则为0。

$$if(p[j]!=\ast )d[i][j]=\{\begin{array}{ll}match(s[i],p[j])& d[i-1][j-1]\\ p[j]!=s[i]& 0\end{array}$$

当p[j]=*的时候,则需判断p[j-1]，如果s[i]=p[j-1]，又因为*代表0或多个，则取决于d[i-1][j]和d[i][j-2]，只要其中一个匹配则成功。如果不相等，则取决于d[i][j-2]（这里直接包括了连续*的情况）。

$$if(p[j]=\ast )d[i][j]=\{\begin{array}{ll}match(s[i],p[j])& d[i-1][j]\Vert d[i][j-2]\\ s[i]!=p[j-1]& d[i][j-2]\end{array}$$ $$match(s[i],p[j])=\{\begin{array}{ll}s[i]=p[j]& 1\\ p[j]=.& 1\\ else& 0\end{array}$$

四、代码

1.递归方法代码如下：

class Solution { public: bool match(string s,string p){ if(p==""){ if(s=="") return true; else return false; }else{ if(p.size()>1&&p[1]=='*'){ int i,j; for(i=3,j=2;i<p.size()&&j<p.size();){ if(p[i]=='*'&&p[i-1]==p[0]) return match(s,p.substr(i-1)); //如果有相同的对应字符，将其合并如"a*a*a*a*a*a*a*a*"，合并为"a*" else if(p[j]=='*') j++; //每两个连续的"*"抵消一个字符串，如a**代表0个字符，a***=a* else break; } if(j%2) return match(s,p.substr(j)); //跳连续的**抵消的匹配字符 if(p[0]=='.'){ if(p.size()==2) return true; //如果匹配字符为.*，则所有字符都匹配 else { for(i=0;i<s.size()+1;i++){ if(match(s.substr(s.size()-i),p.substr(j))) return true; } return false; //对于.*后面还有字符串的，则在s的后缀字符串中找到一个匹配成功即整个匹配成功，否则匹配失败。 } }else { if(s.size()>0&&s[0]==p[0]&&match(s.substr(1),p)) return true; //如果当前s与p第一个字符匹配，则存在两种情况，一种s[0]匹配了一个*（即*未被抵消），一种不匹配（即*当成0被抵消了），只要一种情况为true，匹配就成功。 else return match(s,p.substr(j)); //当前s与p第一个字符不匹配，则肯定不会匹配*（*直接当成0被抵消），则跳过继续递归。 } }else if(s.size()>0&&(p[0]=='.'||s[0]==p[0])) return match(s.substr(1),p.substr(1)); //当前没有*匹配的时候，直接将s,p对应字符匹配，成功则继续递归匹配，否则匹配失败。 else return false; } } bool isMatch(string s, string p) { return match(s,p); } };

递归写法相对不那么清晰，各种情况交叉在一起。

2.动态规划方法代码如下：

class Solution { public: bool match(char s,char p){ if(p!=' '&&s!=' '&&(s==p||p=='.')) return true; else return false; } bool isMatch(string s, string p) { bool d[s.size()+1][p.size()+1]; int i,j,k; char a,b; d[0][0]=true; //两个空字符串匹配不成功 for(i=1;i<s.size()+1;i++){ d[i][0]=false; //当p为空而s不为空时，一定匹配不成功 } for(i=0;i<s.size()+1;i++){ for(j=1;j<p.size()+1;j++){ a=i>0?s[i-1]:' '; //如果s为空则相当于match不匹配的情况。 b=j>1?p[j-2]:' '; //如果p长度为一，考虑单独'*'的情况，相当于d[i][0] if(p[j-1]!='*'){ if(match(a,p[j-1])) d[i][j]=d[i-1][j-1]; else d[i][j]=false; }else{ k=j>2?2:j; if(match(a,b)) d[i][j]=d[i-1][j]||d[i][j-k]; else d[i][j]=d[i][j-k]; } } } return d[s.size()][p.size()]; } };

用动态规划时空复杂度都减小了很多。

---

总结

典型的动态规划思路正则表达式的理解各种特殊情况的考虑，在写代码的时候要考虑边界情况