LeetCode题目：Wildcard Matching

By | 2012 年 11 月 7 日

1.对于开头不是’‘的p，第一个子串必须从s[0]开始匹配
2.对于结尾不是’
‘的p，最后一个子串必须在s的尾巴上匹配

Wildcard Matching
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”, “cab”) → false

Final代码：88ms过大集合

<

pre>
class Solution {
public:
//get pattens splited by ‘‘ or continuous ‘‘s
vector getPattens(const char p) {
vector ret;
int ei = 0;
string *s = NULL;
while(true) {
if(p[ei] == ‘
‘ || p[ei] == ‘\0’) {
if(s) {
//patten found
ret.push_back(*s);
delete s;
s = NULL;
}
if(p[ei] == ‘\0’) break;
} else {
if(!s) {
s = new string();
}
s->push_back(p[ei]);
}
++ei;
}
return ret;
}

int matchStr(const char *s, string &pat, int basei, int baseilmt) {
for(; basei <= baseilmt; ++basei) {
for(int j = 0; j < pat.size(); ++j) {
if(pat[j] != '?' && pat[j] != s[basei + j])
break;
if(j == pat.size() - 1) {
return basei;
}
}
}
return -1;
}

bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s == NULL || p == NULL) return false;

//1. get pattens splited by '*' or continuous '*'s
vector<string> pattens = getPattens(p);
if(pattens.size() == 0) {
if(*p == '*') //p is pure '*'s
return true;
else //p is empty
return *s == '\0';
}

//2. match each patten one by one on s
int slen = strlen(s);
int plen = strlen(p);
int sb = 0;
bool restrictFront = *p != '*';
bool restrictRear = p[plen-1] != '*';
for(int pi = 0; pi < pattens.size() ; ++pi) {
string &pat = pattens[pi];
int sbl = slen - pat.size();

if(sbl < sb) return false;

if(pi == 0 && restrictFront) {
//first patten may be need to match exactly from 0
sbl = 0;
} else if (pi == pattens.size() - 1 && restrictRear) {
//last patten may be need to match exactly from rear of s
sb = slen - pat.size();
sbl = sb;
//cout<<sb<<","<<sbl<<"|";
}

int matchbase = matchStr(s,pat,sb,sbl);
if(-1 == matchbase) {
//cout<<"pat:"<<pi<<","<<pat;
return false;
}
else {
//cout<<sb<<","<<sbl<<","<<pat;
sb = matchbase + pat.size();
}
}
if(pattens.size() == 1) {
if (restrictFront && restrictRear) {
return s[sb] == '\0';
}
//cout<<s[sb];
return true;
}
return true;

for(int i = 0; i < pattens.size(); ++i){
cout<<pattens[i];
cout<<"|";
}
return false;
}

};

class Solution {
public:
bool isMatch(const char *s, const char *p) {
char cs = *s;
char cp = *p;
if(cp == '\0') {
return cs == cp;
} else if (cp == '?') {
if (cs == '\0') return false;
return isMatch(s + 1,p + 1);
} else if (cp == '*') {
const char *st = s;
for(; *st != '\0'; ++st) {
if (isMatch(st, p+1)) return true;
}
return isMatch(st,p+1);
} else if (cp != cs)
return false;
return isMatch(s + 1,p + 1);
}
};

Code rewrite at 2013-1-23

class Solution {
bool isMatch(const char *s, const string &p) {
for(int i = 0; i < p.size(); ++i) {
char cs = *(s+i);
if (cs == '\0') return false;
char cp = p[i];
if (cp != '?' && cp != cs) return false;
}
return true;
}
vector splitPatten(const char *p) {
vector splitp;
string seg="";
int ip = 0;
while(true) {
char c = *(p + ip);
if (c == '\0' || c == '*') {
//a segment found, if seg.size() > 0
if(seg.size() > 0) {
//cout< splitp = splitPatten(p);
//2.0.
if(splitp.size() == 0) {
//all the chararactors in p is *, or, p is empty
if(strlen(p) == 0)
return *s == '\0';
return true;
}
//2.determin if the first seg is fix at front of s and the last seg is fix at the rear of s
bool fixBegin = false,fixEnd = false;
{
if(*p!='*') fixBegin = true;
if(*(p + strlen(p) - 1) != '*') fixEnd = true;
}
//3.go through all the patten's segemnts in p,
//check them one by one in s,
//with the consideration of fixBegin and fixEnd
int si = 0;
const int lens = strlen(s);
for(int i = 0; i < splitp.size(); ++i) {
string &patseg = splitp[i];
//the last available start index in s
int lastsi = lens - patseg.size();
//match is impossible
if(lastsi < si) return false;
int ei = lastsi;
//if this is the first pattern segment and we must match at the beginning of s
if(i==0 && fixBegin) ei = si;
//the similiar situation for last pattern segment
if(i== splitp.size() - 1 && fixEnd) {
si = lastsi;
//the segment must from beginning of s and to ending of s.
if (i==0 && fixBegin && 0!=si) return false;
}

bool matched = false;
for(int iins=si; !matched && iins <= ei; ++iins) {
matched = isMatch(s + iins,patseg);
si = iins + patseg.size();
}
//there is an mismatch
if(!matched) return false;
}
return true;
}
};