Analysis: If there is no * followed, just simple match
if there is a * followed, two scenarios: 1. * and its preceding char are not need; 2. * matches its preceding char for 0~N times
Implementations:
1. Recursive method:
bool isMatch(const char *s, const char *p) { //p is empty if(*p == '\0') return (*s == '\0'); //p is not empty //a * is followed if(*(p + 1) == '*'){ //take 0 preceding element if(isMatch(s, p + 2)) return true; //take 1 or more preceding elements else{ while(*s != '\0' && (*s == *p || *p == '.')){ if(isMatch(s + 1, p + 2)) return true; else s++; } } } //no * is followed else if(*s != '\0' && (*s == *p || *p == '.')) return isMatch(s + 1, p + 1); return false; }
116ms
2. DP method
bool isMatch(const char *s, const char *p){ //get lenght of s and p int m = 0, n = 0; while(s[m] != '\0') m++; while(p[n] != '\0') n++; //dp[i][j]: substring s[0..i-1] and p[0..j-1] match or not vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; //s[0..-1] and p[0..-1] are empty. match for(int i = 1; i <= m; ++i) //p is empty, s is not. never match dp[i][0] = false; for(int j = 2; j <= n; ++j)//s is empty, p is not. only p in pattern (c *)^k can match, such as a*b*c* if(p[j - 1] == '*' && dp[0][j - 2]) dp[0][j] = true; //dp method for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j){ //simple match for no * if(p[j - 1] != '*'){ dp[i][j] = ((s[i - 1] == p[j - 1] || p[j - 1] == '.') && dp[i - 1][j - 1]); } //two scenarios for * if(p[j - 1] == '*'){ dp[i][j] = //1. do not need (c *) to match (j >= 2) && dp[i][j - 2] //2. need (c *) to match || dp[i][j - 1] && (s[i - 1] == p[j - 2] || p[j - 2] == '.') //* matches empty || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'); //* matches c } } return dp[m][n]; //dp[m][n]: s[0..m-1] and p[0..n-1] match or not }
60ms