从头做leetcode之leetcode 10 正则表达式匹配从头做leetcode

10. 正则表达式匹配给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

对于两个字符串的匹配，首先想到的是从第一个字符开始一个一个匹配。但是正则表达式中要处理’.‘和’*'的问题。

关于’.’：由于’.‘是可以匹配任意单个字符，所以这个问题中的’.‘并不是关键问题，只是将原本的两个字符串中目标字符的比较变成了只要p中的字符是’.'就可以了。
关于*：是这个问题的关键问题，因为其可以表示0个或多个前面的元素，所以即使是s与p当前比较的不匹配，只要p之后的一个字符是’*’，那么s也要与从p当前字符之后的第二个字符再开始比较。如果s中有多个相同连续字符且p之后的第一个字符是星号，那么s需要一直向后寻找到第一个不同字符再进行比较
所以想到的用递归的方法。

class Solution { public: bool isMatch(string s, string p) { if(s.size()==0 && p.size()==0) return true; else if(p.size()==0) return false; bool flag=(s.size() != 0)&&(s[0]==p[0] || p[0]=='.'); if(p.size()>1 && p[1]=='*'){ return isMatch(s,p.substr(2)) || (flag && isMatch(s.substr(1),p)); } return flag&&isMatch(s.substr(1),p.substr(1)); } };

通过时间：

文章图片

这样的效率显然是不行的。

在这道题的标签中看到了动态规划，但怎奈我当时学动态规划的时候并没有十分掌握，所以一开始并没有动态规划的想法。

动态规划表达式：如果s[i]==p[j]且dp[i-1][j-1]==true，那么dp[i][j]==true。
同时也要处理如第一种方法中.和*的情况。

class Solution { public: bool isMatch(string s, string p) { s=" "+s; //定义dp数组时防止s，p都为空 p=" "+p; int m=s.size(); int n=p.size(); vector> dp(m+1, vector(n+1, false)); dp[0][0]=true; for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ if(s[i-1]==p[j-1]||p[j-1]=='.'){ dp[i][j]=dp[i-1][j-1]; }else if(p[j-1]=='*'){ if(s[i-1]==p[j-2]||p[j-2]=='.'){ dp[i][j]=dp[i][j-1]||dp[i][j-2]||dp[i-1][j]; }else{ dp[i][j]=dp[i][j-2]; } }else{ dp[i][j]=false; } } } return dp[m][n]; } };

【从头做leetcode之leetcode 10 正则表达式匹配】通过时间：