首页 > 代码库 > leetcode第一刷_Wildcard Matching

leetcode第一刷_Wildcard Matching

又好又难的题。

我发现难题一般都包含了好几个简单题,必须对一些基本的算法熟练掌握才能快速准确的写出代码。这个题就用到了kmp,这个算法写过好多遍,还是不断的出错,哎。

题目中有两种符号,?可以匹配任意单个字符,*可以匹配任意0个或多个字符。?其实没什么,麻烦就麻烦在*上。一个*实际上代表了一段任意的字符串。很容易想到的一种解法是用递归,当p[i]不为*时,看p[i]是不是‘?‘或者p[i]==s[j],这样就把两个串都往下移一个位置,如果p[i]是*的话,一种情况是*代表的是0个字符,那么就只移动p,也可以代表多个字符,一步一步的移动s,代码如下,这种方式是正确的,小规模的数据是可以过得,但是大规模的会超时,因为有*之后支路实在是太多了。

class Solution {
public:
    bool isMatch(const char *s, const char *p) 
    {
    	if (s == NULL || p == NULL) return false;
    	if (*p == ‘\0‘) return *s == ‘\0‘;
    	if (*p == ‘*‘)
    	{
        	while (*p == ‘*‘) ++p;
        	while (*s != ‘\0‘)
        	{
            		if (isMatch(s, p)) return true;
            		++s;
        	} 
        	return isMatch(s, p);
    	}
    	else if ((*s != ‘\0‘ && *p == ‘?‘) || *p == *s)
    	{
        	return isMatch(s + 1, p + 1);
    	}
   	return false;
    }
};
下面介绍一种很巧妙的思路。*可以代表任意一个字符串,那么如果将p按照*来分割的话,剩下的每一段都应该是s的子串,这些子串是有先后顺序的,中间其实是由*来连接的。如果这些子串却是按照顺序匹配了s,那么加上*之后,p和s就会完全匹配。这里有两个边界情况,第一个是如果p的开头不是*,那么分割后p的第一串必须跟s从头开始匹配,不匹配直接返回false。第二个边界是最后一段,如果p的最后一段不是*,那么p的最后一段必须与s的后半部分匹配。

实现的时候,p按照*分割没什么,一个字符一个字符的加就行了,如果是java的话一个split函数就搞定了,注意多个*连在一起的话相当于一个。判断一个字符串是不是子串我用的是kmp,有一个地方特别注意,q[0]=-1而不是0,j的初值也是-1,这里总是搞错。kmp算法的思想是让子串不断的匹配长串,如果子串在位置i出现不匹配的情况,则子串回到前面的某个位置q[i],这个位置使得p[0, q[i]]依然与长串匹配,且q[i]最大。有关kmp可以找matrix67的那篇博客,很精彩的。再加上边界条件的讨论,就可以写出完整的代码了。

我在变量命名的时候犯了个地级错误,但是编译运行是没有问题的,一个算法写到将近100行。。

class Solution {
public:
    int p[100000];
    vector<string> mp;
    bool bs = false, be = false;
    void getp(string &c){
        p[0] = -1;
        int j=-1, i=1;
        while(i<c.length()){
            while(j>=0&&c[j+1]!=c[i]&&c[j+1]!=‘?‘)
                j=p[j];
            if(c[j+1] == c[i] || c[j+1] == ‘?‘)
                ++j;
            p[i] = j;
            ++i;
        }
    }
    int isSubstr(const char* a, string &b){
        getp(b);
        int i=0, j=-1;
        while(a[i]){
            while(j>=0&&b[j+1]!=a[i]&&b[j+1]!=‘?‘)
                j=p[j];
            if(b[j+1] == a[i]||b[j+1] == ‘?‘)
                ++j;
            if(j == b.length()-1)
                return i+1;
            ++i;
        }
        return -1;
    }
    void partS(const char *p){
        string tps;
        while(*p){
            while(*p == ‘*‘)  ++p;
            tps = "";
            for(;*p&&*p!=‘*‘;++p)
                tps += *p;
            if(tps != "")   mp.push_back(tps);
        }
    }
    bool fullcomp(const char *s, string &p, int len){
        for(int i=0;i<len;i++){
            if(s[i] != p[i] && p[i] != ‘?‘)
                return false;
        }
        return true;
    }
    bool isMatch(const char *s, const char *p){
        if(s==NULL && p==NULL)  return false;
        if(*p == ‘\0‘)  return *s == ‘\0‘;
        mp.clear();
        int i=0, j=0, l1=0, l2=0;
        while(s[i]) {++i; ++l1;}
        while(p[j]) {++j; ++l2;}
        partS(p);
        if(mp.size() == 0){
            return true;
        }
        bool firstmatch = false;
        int offset = 0, tpoff;
        if(*p != ‘*‘){
            if(mp.size()==1 && p[l2-1] != ‘*‘){
                if(l1 > l2 || l1==0)
                    return false;
            }
        	if(l1<mp[0].length()||!fullcomp(s, mp[0], mp[0].length()))
        		return false;
        	offset += mp[0].length();
        	firstmatch = true;
        }
        vector<string>::iterator it=mp.begin();
        if(firstmatch)	++it;
        for(;it!=mp.end()&&offset<l1;++it){
            if(l1-offset<(*it).length())    return false;
            tpoff = isSubstr(s+offset, *it);
            if(tpoff == -1)    return false;
            offset += tpoff;
        }
        if(it!=mp.end()){
            return false;
        }
        if(p[l2-1] != ‘*‘){
			for(int i=0;i<mp[mp.size()-1].length();i++){
				if(p[l2-i-1] != s[l1-i-1] && p[l2-i-1] != ‘?‘)
					return false;
			}
		}
        return true;
    }
};