首页 > 代码库 > [LeetCode #10] Regular Expression Matching
[LeetCode #10] Regular Expression Matching
Implement regular expression matching with support for ‘.‘ and ‘*‘.
‘.‘ Matches any single character.‘*‘ Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true1 class Solution { 2 public: 3 bool isMatch(string s, string p) { 4 int m = s.size(), n = p.size(); 5 6 vector<vector<bool>> dp (m+1, vector<bool> (n+1, false)); 7 8 dp[0][0] = true; 9 10 for (int i = 0; i < m; i++){11 dp[i+1][0] = false;12 }13 14 for (int j = 0; j < n; j++){15 dp[0][j+1] = j > 0 && p[j] == ‘*‘ && dp[0][j-1];16 }17 18 for (int i = 0; i < m; i++){19 for (int j = 0; j < n; j++){20 if (p[j] != ‘*‘){21 dp[i+1][j+1] = dp[i][j] && (s[i] == p[j] || p[j] == ‘.‘);22 }else{23 dp[i+1][j+1] = dp[i+1][j-1] || ((dp[i][j+1]) && (s[i] == p[j-1] || p[j-1] == ‘.‘));24 }25 }26 }27 28 return dp[m][n];29 }30 };
[LeetCode #10] Regular Expression Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。