1 KMP
Implement strStr()
Total Accepted: 15450 Total
Submissions: 71217My Submissions
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
class Solution { public: char *strStr(char *haystack, char *needle) { int n=strlen(needle); if(n==0) return haystack; //kmp vector<int> nxt(n+1);///@error: nxt should be sized n+1, not n. to contain the nxt[n] nxt[0]=-1;nxt[1]=0; for(int i=0;i<n;i++){ int j=nxt[i]; while(j>=0&&needle[i]!=needle[j]) j=nxt[j]; //i matched j nxt[i+1]=j+1;/////@@@@@@@error: nxt[i+1]=j+1; mistake as needle[i+1]=j+1; an Array_Variable_Fault !!!! } int j=0; for(int i=0;haystack[i]!=0;i++,j++){ while(j>=0&&haystack[i]!=needle[j]) j=nxt[j];//i matched j if(j==n-1) return haystack+i-j; //matche needle } return NULL; } };
正则匹配不同于一般匹配。回溯取决于*号出现的位置。
采用贪心法:p中'*'尽量匹配s中最少的字符,从上到下执行规则:
1.1 如果p到达0,s未到达0: 则回溯或匹配失败
1.2 如果p到达0,s到达0: 则成功
2.1 如果p为'*':设置回溯点,p前进
3.1 如果p不为0或'*',而s到达0: 则匹配失败
3.2 如果p不为0或'*',s不为0: p=s或p='?'则s、p前进;否则回溯或匹配失败。
Wildcard Matching
Total Accepted: 10189 Total
Submissions: 75093My Submissions
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) { const char *pre_s,*pre_p;bool star=false;///@@error:pre_s pre_p must be const, or invalid conversion from 'const char*' to 'char*' [-fpermissive] while(true){ if(*p==0){ if(*s==0) return true; //*p=0 and *p matches *s if(!star) return false; //*p=0!=*s s=++pre_s;p=pre_p; } else if(*p!='*'){ if(*p==*s||*p=='?'&&*s!=0) s++,p++;//*p!=0 and *p matches *s (then *s!=0) else { if(!star||*s==0) return false;///@warning:when *s=0,say s reaches the end,p will not match it even if Star=true s=++pre_s;p=pre_p; } }else{ star=true; pre_s=s,pre_p=p+1; p=pre_p; } } } };
或者
class Solution { public: bool isMatch(const char *s, const char *p) { // Start typing your C/C++ solution below // DO NOT write int main() function const char *pre_s = s, *pre_p = p;//保存上一次开始匹配的位置 bool has_star = false; while (*s) { if (*s != *p) { if (*p == '?') s++, p++; else if (*p == '*') { has_star = true; while (*p == '*') p++; if (*p == '\0') return true; pre_s = s, pre_p = p;//置上一个开始比较的位置 } else if (has_star) { pre_s++; s = pre_s, p = pre_p;//恢复到上一次比较的下一个位置 } else return false; //*s!=0 and *s!=*p and *p!='?' and !hasStar } else s++, p++; } //s has reach the end, so p's remainning part must match ''. while (*p == '*') p++; return *p == '\0'; } };
或者:
class Solution { public: bool isMatch(const char *s, const char *p) { bool tag = false; const char * pre_s, *pre_p; while(*s){ if(*s==*p || *p=='?') s++, p++; else if(*p=='*'){ tag = true; pre_s = s, pre_p = ++p; } else{ if(tag){ s = ++ls, p = pre_p; } else return false; } } while(*p == '*') p++; return *p==0; } };
Regular Expression Matching
Total Accepted: 13590 Total
Submissions: 68280My Submissions
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