[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") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
DiffcultyHard
Similar Problems
[LeetCode 44] Wildcard Matching Hard
Analysis
// http://articles.leetcode.com/2011/09/regular-expression-matching.html bool isMatch(const char s, const char p) { if(s == NULL || p == NULL) return false; // assert() if (p == '\0') return s == '\0';
// next char is not '*': must match current character
if (*(p+1) == '*') {
if(*p != '*') return false;
return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
}
// next char is '*'
while ((*p == *s) || (*p == '.' && *s != '\0')) {
if (isMatch(s, p+2)) return true;
s++;
}
return isMatch(s, p+2);
}
// 4 ms // https://leetcode.com/discuss/51865/my-4ms-dp-solution-another-recursive-version-also-given-72ms / Just to build a DP table checked, where checked[i][j] indicates whether s[0..i-1] matches with p[0..j-1]. The recursive relationship is as below: (1) To match with the empty string s[0..0], (i.e. to make checked[0][j]), P[0..j-1] has to meet: p[j-1]=='' (to cancel p[j-2]) and checked[0][j-2] == true; (2) To match with the string s[0..i-1] (i.e. to make checked[i][j]), P[0..j-1] has to meet: if p[j-1] =='', then j must be larger than 1 (j>1) and checked[i][j-2] (i.e. p[j-2] cancelled by '') checked[i-1][j] && (s[i-1] ==p[j-2] || p[j-2] =='.') (s[i-1] matches with p[j-2] or '.', ) if p[j-1] !='', checked[i-1][j-1] && (s[i-1] ==p[j-1] || p[j-1] =='.')(i.e. s[i-1] matches with p[j-1] or '.') / class Solution { public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); int i, j; bool checked[m+1][n+1];
for(j = 2, checked[0][0] = true, checked[0][1] = false; j <= n; ++j) // match s[0..0]
checked[0][j] = p[j-1] == '*'? checked[0][j-2] : false;
for(i = 1; i <= m; ++i)
for(j = 1, checked[i][0] = false; j <= n; ++j){
if(p[j-1] == '*') // case (1)
checked[i][j] = (j>1) && ( checked[i][j-2] || ( ( checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')) );
else // case (2)
checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
}
return checked[m][n];
}
};
// 9 ms
// https://leetcode.com/discuss/43860/9-lines-16ms-c-dp-solutions-with-explanations
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector
// By the way, you may merge the two "for" loops into one.
class Solution {
public:
bool isMatch(string s, string p) {
// dynamic programming
int m = s.length(), n = p.length();
// vector
// 12ms
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector
for(int i = 0; i < m + 1; i++) {
for(int j = 1; j < n + 1; j++) {
if(p[j-1]!='.' && p[j-1] != '*') {
if(i>0 && s[i-1]==p[j-1] && dp[i-1][j-1])
dp[i][j] = true;
}
else if(p[j-1]=='.') {
if(i>0 && dp[i-1][j-1])
dp[i][j] = true;
}
else if(j>1) { //'*' cannot be the 1st element
if(dp[i][j-1] || dp[i][j-2]) // match 0 or 1 preceding element
dp[i][j] = true;
else if(i>0 && (p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j]) // match multiple preceding elements
dp[i][j] = true;
}
}
}
return dp[m][n];
}
};
// 20 ms bool isMatch(const char s, const char p) { if (p == '\0') return s == '\0'; if ((p + 1) == '') return isMatch(s, p+2) || ((p == '.' && s != '\0') || s == p) && isMatch(s + 1, p); if (p == '.') return s != '\0' && isMatch(s + 1, p + 1); return s == p && isMatch(s + 1, p + 1); }
// 32 ms class Solution { public: bool isMatch(const char s, const char p) { for( char c = p; c != 0; ++s, c = p ) { if((p+1) != '') p++; else if(isMatch(s, p+2)) return true; if( (s==0) || ((c!='.') && (c!=s)) ) return false; } return *s == 0; } };
// 32ms class Solution { public: bool isMatch(const char s, const char p) { if (p == '\0') return s == '\0'; //empty
if (*(p + 1) != '*') {//without *
if(!matchFirst(s, p)) return false;
return isMatch(s + 1, p + 1);
} else { //next: with a *
if(isMatch(s, p + 2)) return true; //try the length of 0
while (matchFirst(s, p)) //try all possible lengths
if (isMatch(++s, p + 2)) return true;
}
}
bool matchFirst(const char *s, const char *p){
return (*p == *s || (*p == '.' && *s != '\0'));
}
};
// 72ms class Solution { public: bool isMatch(string s, string p) { helper(s, p, 0, 0); }
private: bool helper(const string &s, const string &p, int sS, int pS) { int m = s.size(), n = p.size(), i, j; if(pS==n) return sS ==m; // if p goes to its end, then only if s also goes to its end to return true;
if(p[pS+1]!='*')
{
if( sS<m && (p[pS]==s[sS] || p[pS] == '.')) return helper(s, p, sS+1, pS+1);
}
else
{
if(helper(s, p, sS,pS+2)) return true;
while(sS<m && (p[pS]==s[sS] || p[pS] == '.')) if(helper(s,p, ++sS, pS+2)) return true;
}
return false;
}
};
// 778 ms class Solution { public: bool isMatch(string s, string p) { int ns = s.length(), np = p.length(); if (np == 0) { return ns == 0; } if (np == 1) { return ns == 1 && (p.at(0) == '.' || p.at(0) == s.at(0)) ; } // np i bigger than 1 here if (p.at(1) == '*') { if (isMatch(s, p.substr(2, np - 2))) { return true; } return ns > 0 && (p.at(0) == '.' || s.at(0) == p.at(0)) && isMatch(s.substr(1, ns - 1), p); } else { return ns > 0 && (p.at(0) == '.' || s.at(0) == p.at(0)) && isMatch(s.substr(1, ns - 1), p.substr(1, np - 1)); } }
};