首页 > 代码库 > Regular Expression Matching
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") → true
这道题难度等级：Hard。我看了提示，说要使用Dynamic Programming、Backtracking。恶补了一下这两个方面的知识，结果还是没做出来。后来想到了递归，大体思路已经正确，可是细节之处总是处理不好。此题，寡人败了。
我查阅了很多文章，下面的解法在简洁性和易懂性上，无人能出其右。
solution1：(递归)
bool isMatch(const char *s, const char *p) { if (!*p) return (!*s); if (‘*‘ == *(p + 1)) { // x* matches empty string or at least one character: x* -> xx* // *s is to ensure s is non-empty return (isMatch(s, p + 2) || *s && (*s == *p || ‘.‘ == *p) && isMatch(s + 1, p)); } else { if (!*s) return false; return (*s == *p || ‘.‘ == *p) ? isMatch(s + 1, p + 1) : false; }}
solution2：(动态规划)
bool isMatch(const char *s, const char *p) { int i, j; int m = strlen(s); int n = strlen(p); /** * b[i + 1][j + 1]: if s[0..i] matches p[0..j] * if p[j] != ‘*‘ * b[i + 1][j + 1] = b[i][j] && s[i] == p[j] * if p[j] == ‘*‘, denote p[j - 1] with x, * then b[i + 1][j + 1] is true if any of the following is true * 1) "x*" repeats 0 time and matches empty: b[i + 1][j -1] * 2) "x*" repeats 1 time and matches x: b[i + 1][j] * 3) "x*" repeats >= 2 times and matches "x*x": s[i] == x && b[i][j + 1] * ‘.‘ matches any single character */ //bool b[m + 1][n + 1]; vector< vector<int> > b(m+1,vector<int>(n+1)); b[0][0] = true; for (i = 0; i < m; i++) { b[i + 1][0] = false; } // p[0..j - 2, j - 1, j] matches empty iff p[j] is ‘*‘ and p[0..j - 2] matches empty b[0][1] = false; for (j = 1; j < n; j++) { b[0][j + 1] = ‘*‘ == p[j] && b[0][j - 1]; } for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (p[j] != ‘*‘) { b[i + 1][j + 1] = b[i][j] && (‘.‘ == p[j] || s[i] == p[j]); } else { b[i + 1][j + 1] = b[i + 1][j - 1] && j > 0 || b[i + 1][j] || b[i][j + 1] && j > 0 && (‘.‘ == p[j - 1] || s[i] == p[j - 1]); } } } return b[m][n]; }
原文链接：https://oj.leetcode.com/discuss/18970/concise-recursive-and-dp-solutions-with-full-explanation-in
Regular Expression Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。