leetcode 10. Regular Expression Matching(dp)
发布时间:2020-12-14 06:42:45 所属栏目:百科 来源:网络整理
导读:题目:https://leetcode.com/problems/regular-expression-matching/description/ 题意:给你字符串s、p,让判断s是否符合p的正则匹配 ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. 思路:令dp[i][j]代表s[0…
题目:https://leetcode.com/problems/regular-expression-matching/description/
class Solution {
public:
bool dp[1005][1005];
bool isMatch(string s,string p) {
memset(dp,false,sizeof(dp));
dp[0][0] = true;
for(int i = 0;i <= s.length();i++){
for(int j = 1;j <= p.length();j++){
if(i >= 1 && s[i-1] == p[j-1] || p[j-1] == '.')
dp[i][j] = dp[i][j] || dp[i-1][j-1];
if(p[j-1] == '*'){
if(i >= 1 && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))//>0
dp[i][j] = dp[i][j] || dp[i - 1][j];
dp[i][j] = dp[i][j] || dp[i][j - 2];//0
}
}
}
return dp[s.size()][p.size()];
}
};
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |