►►►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
Method 1: Recursive
Space: O(n) Running Time :O(n^2) 32ms
1) '.' is easy to handle. if p has a '.', it can pass any single character
in s except '\0'.
2) '*' is a totally different problem. if p has a '*' character, it can pass
any length of first-match characters in s including '\0'.
bool matchOne(const char *s, const char *p){
return (*p == *s || (*p == '.' && *s != '\0'));
}
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0'; //empty
if (*(p + 1) != '*') {//without *
if(!matchOne(s,p)) return false;
return isMatch(s + 1, p + 1);
} else { //next: with a *
//try the length of 0
if(isMatch(s, p + 2)) return true;
while ( matchOne(s,p) ) //try all possible lengths
if (isMatch(++s, p + 2)) return true;
}
}
Method 2: DP
Transform method1 into DP with record duplicated subproblem
Space: O(n*m) Running Time :O(n*m) 4ms
bool matchOne(const char s, const char p){
return (p == s || (p == '.' && s != '\0'));
}
bool helper(const char*s, const char *p, int i, int j, int n, int m, int V[n
+1][m+1]){
if(V[i][j] != -1) return V[i][j];
bool ret;
if (p[j+1] != '*') {//without *
if(!matchOne(s[i], p[j])) {
V[i][j] = 0;
return false;
}
ret = helper(s, p, i+1, j+1, n, m, V);
V[i][j] = ret ? 1 : 0;
return ret;
} else { //next: with a *
//try the length of 0
ret = helper(s, p, i, j+2, n, m, V);
if(ret) {
V[i][j] = 1;
return true;
}
int ii = i;
while( matchOne(s[ii],p[j]) ) {//try all possible lengths
ret = helper(s, p, ++ii, j+2, n, m, V );
if(ret) {
V[i][j] = 1;
return true;
}
}
}
V[i][j] = 0;
return false;
}
bool isMatch(const char*s, const char *p){
int n = strlen(s);
int m = strlen(p);
int i,j;
int V[n+1][m+1];
for(i=0;ifor(j=0;jV[i][j] = -1;
V[n][m] = 1;
// init right
for(i=n-1;i>=0;i--) V[i][m] = 0;
// init bottom
for (j=m-1; j>=0;j--){
if (p[j+1]=='*') V[n][j] = V[n][j+2];
else V[n][j] = 0;
}
return helper(s, p, 0, 0, n, m, V);
}
Method 3: DP fill in dp from bottom right
Space: O(n*m) Running Time :O(n*m) 4ms
bool matchOne(const char *s, const char *p){
return (*p == *s || (*p == '.' && *s != '\0'));
}
bool isMatch(const char *s, const char *p) {
int n = strlen(s);
int m = strlen(p);
int i,j;
bool V[n+1][m+1];
for(i=0;ifor(j=0;jV[i][j] = false;
V[n][m] = true;
// init bottom
for (i=0; i// init right
for (j=m-1; j>=0;j--){
if (p[j]=='\0') V[n][j]=true;
if (p[j+1]=='*') V[n][j]=V[n][j+2];
}
// fill in dp from bottom right
for (j=m-1; j>=0; j--){
if (p[j]=='*') continue;
for (i=n-1; i>=0; i--){
if (p[j+1]!='*')
V[i][j] = (s[i]==p[j]||p[j]=='.') ?
V[i+1][j+1] :
false;
else if (V[i][j+2]){ //try the length of 0
V[i][j] = true;
} else {
V[i][j] = (s[i]==p[j]||p[j]=='.') ?
V[i+1][j] :
false;
}
}
}
return V[0][0];
}