A 20ms solution based on the kmp search


  • 0
    Y
    class Solution {
    public: bool isMatch(string s, string p){
    	const char* text= s.c_str();
    	int tlen= s.size();
    	const char* pat = p.c_str();
    	int max_plen=p.size();
    
    	// check if the left most subtring not containing * of p matches the corresponding subtring of s
    	for (; tlen > 0 && (text[0] == pat[0] || pat[0] == '?') && pat[0] != '*'; text++, pat++, max_plen--, tlen--);
    	if (max_plen > 0 && pat[0] != '*') return false;
    	
    	// check if the right most subtring not containing * of p matches the corresponding subtring of s
    	for (; tlen > 0 && max_plen > 0 && (text[tlen - 1] == pat[max_plen - 1] || pat[max_plen - 1] == '?'); tlen--, max_plen--);
    	if (max_plen == 0) { return tlen == 0; }
    	else if (max_plen > 0 && pat[max_plen - 1] != '*') return false;
    
    	//the substring of p in the form of *p1*p2*...pn* ,  where p1...,pn is string not containg *
    	//sequently checking if every pi is in s
    	int plen;
    	while (true) {
    		while (*pat == '*') {
    			pat++;
    			max_plen--;
    		}
    		plen = 0;
    		for (; plen< max_plen && pat[plen] != '*'; plen++);
    		int pos = kmp(text, tlen, pat, plen);
    		if (pos < 0) return false;
    		text += pos + plen;
    		tlen -= pos + plen;
    		pat += plen;
    		max_plen -= plen;
    		if (max_plen == 0) return true;
    
    	}
    }
    
    // if text contains pat , return the postion of the first match, else return -1
    int kmp(const char* text, int tlen, const char* pat, int plen) {
    	if (plen == 0) return 0;
    	vector<int> nexts(plen + 1, 0);
    	for (int i = 2; i <= plen; i++) {
    		for (int j = i; j > 0;) {
    			if (pat[j - 1] == '?' || pat[i - 1] == pat[nexts[j - 1]]) {
    				nexts[i] = nexts[j - 1] + 1;
    				break;
    			}
    			else if (pat[nexts[j - 1]] == '?') {
    				int m = j - 1, n = nexts[j - 1], temp;
    				do {
    					temp = m;
    					m = n;
    					n = 2 * n - temp;
    				} while (pat[n] == '?'&& n > 0);
    				if (n>0 && pat[n] != '?'&& pat[n] != pat[j - 1])
    					j = nexts[j - 1];
    				else {
    					nexts[i] = nexts[j - 1] + 1;
    					break;
    				}
    			}
    			else j = nexts[j - 1];
    		}
    	}
    	int i = 0, j = 0;
    	while (i<tlen) {
    		for (; i<tlen && j< plen && (text[i] == pat[j] || pat[j] == '?'); i++, j++);
    		if (j == plen) return i - j;
    		for (; j > 0 && text[i] != pat[j] && pat[j] != '?'; j = nexts[j]);
    		if (text[i] != pat[j] && pat[j] != '?') {
    			i++;
    			j = 0;
    		}
    	}
    	return -1;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.