正则表达式匹配

又是以前写过的题，现在相当于时复盘。

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

输入：s = "aa" p = "a"fu
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/regular-expression-matching

遇到字符串相关的题，考虑动态规划。如何定义base case，和状态转移方程呢？

对于s,p两个字符串，分别用两个指针，i，j指向，dp[i][j]表示s[0...i]与p[0...j]是否匹配。dp[0][0]=true,两个空串必然是匹配的。

我们分情况来讨论，判断当前符号是否匹配，如果匹配那么p[i][j]=p[i-1][j-1],如果不匹配，就看看当前符号是不是'*',如果是’*‘则分情况讨论。

为*，

1. p[j-1]!=s[i]&&dp[j-1]!='.' dp[i][j]=dp[i][j-2]

2.p[j-1]==s[i]||dp[j-1]=='.' dp[i][j]=dp[i][j-1] || dp[i-1][j] || dp[i][j-2]

dp[i][j]=dp[i][j-2]//不匹配

dp[i][j]=dp[i][j-1]//匹配一个

dp[i][j]=dp[i-1][j]//匹配多个

代码如下：

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         s=" "+s;//防止该案例：""
"c*"
 5         p=" "+p;
 6         int m=s.size(),n=p.size();
 7         bool dp[m+1][n+1];
 8         memset(dp,false,(m+1)*(n+1));
 9         dp[0][0]=true;
10         for(int i=1;i<=m;i++){
11             for(int j=1;j<=n;j++){
12                 if(s[i-1]==p[j-1] || p[j-1]=='.'){
13                     dp[i][j]=dp[i-1][j-1];
14                 }
15                 else if(p[j-1]=='*'){
16                     if(s[i-1]!=p[j-2] && p[j-2]!='.')
17                         dp[i][j]=dp[i][j-2];
18                     else{
19                         dp[i][j]=dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
20 
21                     }
22                 }
23             }
24         }
25         return dp[m][n];
26     }
27 };