一 、通配符匹配(递归和非递归):
Implement wildcard pattern matching with support for'?'
and'*'
.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
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","*") → true
isMatch("aa","a*") → true
isMatch("ab","?*") → true
isMatch("aab","c*a*b") → false
class Solution { public: bool isMatch(const char *s,const char *p) { // Start typing your C/C++ solution below // DO NOT write int main() function /* recursive solution (TLE) if(*p == 0 && *s == 0){ return true; } if(*s == 0){ while(*p == '*') ++p; return !(*p); } if(*p == 0){ return false; } int i = 0; for(; p[i] && s[i]; ++i){ if(p[i] == s[i] || p[i] == '?') continue; if(p[i] == '*'){ return isMatch(s+i,p+i+1) || isMatch(s+i+1,p+i); } else{ return true; } } return isMatch(s+i,p+i); */ //dp solution /* dp[i][j] = 1 means s[1~i] 和 p[1~j] match。 so: if p[j] == '*' && (dp[i][j-1] || dp[i-1][j]) dp[i][j] = 1 else p[j] = ? || p[j] == s[i] dp[i][j] = dp[i-1][j-1]; else dp[i][j] = false; */ int len_s = strlen(s); int len_p = strlen(p); const char* tmp = p; int cnt = 0; while(*tmp) if(*(tmp++) != '*') cnt++; if(cnt > len_s) return false; vector<vector<bool> > dp(len_s+1,vector<bool>(len_p+1,false)); dp[0][0] = true; for(int i = 1; i <= len_p; ++i){ if(dp[0][i-1] && p[i-1] == '*') dp[0][i] = true; for(int j = 1; j <= len_s; ++j){ if(p[i-1] == '*'){ dp[j][i] = dp[j-1][i] || dp[j][i-1]; } else if(p[i-1] == '?' || p[i-1] == s[j-1]){ dp[j][i] = dp[j-1][i-1]; } else{ dp[j][i] = false; } } } return dp[len_s][len_p]; } };
二、正则表达式匹配(递归和非递归)
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,"a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true
class Solution { public: bool isMatch(const char *s,const char *p) { // Note: The Solution object is instantiated only once and is reused by each test case. /*recursive solution if(0 == *p) return 0 == *s; if(*(p+1) != '*'){ if(*p == *s || (*p == '.' && 0 != (*s))){ return isMatch(s+1,p+1); } return false; } else{ while(*p == *s || (*p == '.' && 0 != (*s))){ if(isMatch(s,p+2)){ return true; } s++; } return isMatch(s,p+2); } */ //dp solution(sunbaigui) int len_s = strlen(s); int len_p = strlen(p); vector<vector<bool> > dp(len_s+1,false)); dp[0][0] = true; for(int i = 0; i <= len_s; ++i){ char preChar = '\0'; int preIdx = 0; for(int j = 1; j <= len_p; ++j){ if(0!=i && (p[j-1] == '.' || p[j-1] == s[i-1])){ dp[i][j] = dp[i-1][j-1]; } else if(p[j-1] == '*'){ if(0 != i && (preChar == '.' || preChar == s[i-1])){ dp[i][j] = dp[i-1][j] || dp[i][j-1]; } dp[i][j] = dp[i][j] || dp[i][preIdx]; } if(p[j-1] != '*') { preChar = p[j-1]; preIdx = j-1; } } } return dp[len_s][len_p]; } };