LeetCode 10. 正则表达式匹配(EASY to Understand)
原题链接
困难
作者:
Vodka编程菜菜
,
2020-06-04 09:32:23
,
所有人可见
,
阅读 704
C++ 代码
class Solution {
public:
bool isMatch(string s, string p) {
int len_s = s.size();
int len_p = p.size();
vector<vector<bool>> dp(len_s+1, vector<bool>(len_p+1, false));
dp[0][0] = true;
// i need to start from 0 instead of 1
// Since may have S = "", P = "A*"
for(int i =0; i <=len_s; ++i){
for(int j =1; j <= len_p; ++j){
if( i > 0 && (s[i-1]==p[j-1] || p[j-1]=='.')) {
dp[i][j] = dp[i][j] || dp[i-1][j-1];
}else if(p[j-1]=='*' && j>=2){
if(i > 0 && (p[j-2]== s[i-1] || p[j-2]=='.')){
dp[i][j] = dp[i][j] || dp[i-1][j];
}
dp[i][j] = dp[i][j] || dp[i][j-2];
}
}
}
return dp[len_s][len_p];
}
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
作者:Vodka编程菜菜
链接:https://www.acwing.com/activity/content/code/content/335576/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。