力扣刷题|力扣刷题（剑指 Offer 19. 正则表达式匹配）dp 力扣刷题|大数据

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

输入: s = "aab" p = "c*a*b" 输出: true

思路：动态规划
首先建立一个行数为m+1，列数为n+1的一个二维数组，如下表所示，多一行和一列是为了判断字符串p能否满足行为空的情况。
首先dp[0][0]表示此时s和p均为空，那么s和p肯定是相等的，所有设置为true
然后初始化第一行，第一行表示s为空的时候，此时只有利用p中*来不断消除其前面的字符从而达到p为空才能满足相等，所有需要从p的1位置每次+2开始检查该位置是否为*，如果是就为1，不是就退出
正式遍历的时候，其实每个位置主要分为两种情况，一种是*一种不是*：
*：如果要为true，只有三种情况。1、前面的字符出现次数为0，此时dp[i][j]=dp[i][j-2]
2、前面的字符出现次数为1，要满足s[i-1]==p[j-2], 或者p[j-2]=="."，dp[i][j]=dp[i][j-1];
3、前面的字符出现多次，那么要满足s[i-1]==p[j-2], 或者p[j-2]=="."，dp[i][j]=dp[i-1][j];
不为*：满足s[i-1]==p[j-1], 或者p[j-1]=="."，dp[i][j]=dp[i-1][j-1]; 看两个字符的前一个字符是否比较成功

		c	*	a	*	b
	1	0	1	0	1	0
a	0	0	0	1	1	0
a	0	0	0	0	1	0
b	0	0	0	0	0	1

class Solution { public: bool isMatch(string s, string p) { int m=s.size(),n=p.size(); vector> dp(m+1,vector(n+1,false)); //对于第一行而言要为true,就只有为空的时候，也就是p的偶数位置要为* dp[0][0]=true; for(int i=2; i<=n; i+=2){ if(p[i-1]=='*')dp[0][i]=true; else break; } //下面就是对其他行进行判断，主要分为两种情况，一种是该位置为*，一种是该位置不为* for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(p[j-1]=='*'){//0个、1个、多个 dp[i][j]=(dp[i][j-2]||((p[j-2]==s[i-1]||p[j-2]=='.')&&(dp[i][j-1]||dp[i-1][j]))); } else{ if(p[j-1]=='.'||p[j-1]==s[i-1])dp[i][j]=dp[i-1][j-1]; } } } return dp[m][n]; } };

【力扣刷题|力扣刷题（剑指 Offer 19. 正则表达式匹配）dp】