LeetCode题目:Wildcard Matching

By | 2012 年 11 月 7 日

这题有点困难。
一开始用很直观的递归算法:逐个看p字符串的字符,针对不同的可能性,’‘,’?’,普通字符进行处理。但是遇到’‘的时候需要递归。这个算法很容易写出来,小集合过了,但是大集合会超时。

然后看一个贪心算法,只需要依据连续的’‘,将p分割成一些不带’‘的子串。然后在s中依次匹配就好了,只不过需要特殊照顾一下首尾两个子串:
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;
}

};



递归代码
这是正确的代码,小集合4ms过了,但是大集合超时。

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;
    }
};

2 thoughts on “LeetCode题目:Wildcard Matching

发表评论

电子邮件地址不会被公开。 必填项已用*标注