公众号merlinsea
链接：
https://leetcode.cn/problems/regular-expression-matching/
解题思路：
如果 p[j+1] == *
Char ch = p[j]
If ch==. 取决于p[0,j-1] 和s[0,i-1]是否匹配
If ch!=. 取决于p[0,j] 和s[0,i]是否匹配 且 p[j+1]==s[i+1]
匹配0个元素 p[0,j] 和s[0,i+1]是否匹配
如果 p[j+1] == .
当前匹配情况取决于之前的元素是否匹配---->p[0,j+1]匹配s[0,i+1]
如果 p[j+1] == 英文字符
当前匹配情况取决于之前的元素是否匹配且当前元素是否相等----》p[j+1]==s[i+1]
题目初步计算求解过程：
原题的进阶理解过程：
解题代码
class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); vector<vector<bool>> dp(m+1,vector<bool>(n+1,false)); dp[0][0] = true; for(int j=1;j<=n;j++){ if(p[j-1]=='*'){ dp[0][j]=dp[0][j-2]; } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(p[j-1]=='.'){ dp[i][j] = dp[i-1][j-1]; }else if(p[j-1]=='*'){ //回退一个字符 bool flag1 = dp[i][j-2]; //匹配0个元素字符 bool flag2 = dp[i][j-1]; //ch表示前面是什么字符 char ch = p[j-2]; //*代表重复元素 bool flag3 = false; if(ch == '.'){ flag3 = dp[i-1][j-1] || dp[i-1][j]; }else if(ch != '*'){ flag3 = (dp[i-1][j-1]|| dp[i-1][j]) && (s[i-1]==ch); }else{ //当前字符是* flag3 = dp[i][j-1]; } dp[i][j] = flag1 || flag2 || flag3; }else{ if(p[j-1]==s[i-1]){ dp[i][j]=dp[i-1][j-1]; } } } } return dp[m][n]; } };
关于leetcode算法训练营:
加我微信号私聊参加训练营～
本人用c++刷了800道左右的算法，java语言刷了600道左右的算法题，并对这些题做了详细的个人总结。本科期间系统学习了数据结构与算法课程，同时考研过程中写完了率辉主编的《2020年数据结构高分笔记》和《数据结构1000题》，看完的视频包括《mooc浙大数据结构国家精品课程》和《王道考研408数据结构课程》，《王道2019年算法题讲解视频》，最终以初试专业第三名进入了北理工软件工程专业。熟悉并掌握常见的数据结构，比如链表、数组、树、图、队列、堆栈等等，精通数据结构教材中的所有算法，比如常见的遍历算法、动态规划，递归，回溯，剪枝，并查集，最短路径，拓扑排序等，所以快加入训练营吧，我们一起进步
奔跑的小梁，公众号：梁霖编程工具库我决定了，算法文档开源！！
