Help me! Exhausted. Need a more well-formed solution.


  • 0

    Ahhhhhhhhhhhhh!
    The following is my first solution which got TLE for long input.

    // TLE Solution
    class Solution {
    private:
    	bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
    public:
        bool isMatch(const char *s, const char *p) {
        	if(!s || !p) return !s && !p;
        	// match single char
        	while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
        	if(!*p) return !*s;
        	if(*p != '*') return false;
        	// match '*'
        	while(*p == '*') ++p;
        	if(!*p) return true; 
        	while(*s){
        		if(sameChar(*s, *p) && isMatch(s, p)) return true; // This line is inefficient!
        		++s;
        	}
        	return false;
        }
    };
    

    The line followed with a comment is the cause of TLE. In the light of @greed's solution, I added some lines in the while loop.

    // AC Solution. I felt it's a little bit redundant, but I failed to simplify it.
    class Solution {
    private:
    	bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
    public:
        bool isMatch(const char *s, const char *p) {
        	if(!s || !p) return !s && !p;
        	// match single char
        	while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
        	if(!*p) return !*s;
        	if(*p != '*') return false;
        	// match '*'
        	while(*p == '*') ++p;
        	if(!*p) return true;
        	while(*s){
        		const char *ts = s, *tp = p;
        		while(*ts && *tp && sameChar(*ts, *tp)){ ++ts; ++tp; }
        		if(!*tp && !*ts) return true;
        		if(*tp == '*') return isMatch(ts, tp);
        		if(!*ts) return false; // This line is very very important!
        		// If s doesn't have enough char to match p, return false directly!
        		++s;
        	}
        	return false;
        }
    };
    

    The line if(!*ts) return false; plays a vital role to stop immediately for impossible case . But I'm not satisfied. I feel that the lines in the while loop are very similar to the three lines that match single chars. Seemingly it's repeating itself. I sat in front of my computer for two hours trying to simplify the code, but in the end I can only persuade myself it's irreducible. The following lines are my final submission. Can anyone give me a more elegant solution?

    // AC Solution. I can only extract a function `guessStartlet` out of `isMatch`.
    class Solution {
    private:
    	bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
    	void skipSameChar(const char *&s, const char *&p){
    		while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
    	}
    	bool guessStarlet(const char *s, const char *p){
    		while(*p == '*') ++p; // need only one '*'
    		if(!*p) return true; // p ends with '*'
    		while(*s){
    			const char *ts = s, *tp = p;
        		skipSameChar(ts, tp);
        		if(!*tp && !*ts) return true;
        		if(*tp == '*') return guessStarlet(ts, tp);
        		if(!*ts) return false;
        		++s;
    		}
    		return false;
    	}
    public:
    	bool isMatch(const char *s, const char *p) {
    		if(!s || !p) return !s && !p;
    		// match single char
    		skipSameChar(s, p);
    		if(!*p) return !*s;
    		if(*p != '*') return false;
    		// match '*'
    		return guessStarlet(s, p);
    	}
    };

  • 0
    R

    Share my DP solution:

    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            if( !s || !p ) return !s && !p;
            int N = strlen(s), M = strlen(p);
            
            vector<int> lenl(M+1),lenr(M+1);
            lenr[M] = lenl[0] = 0;
            for(int j=M-1;j>=0;j--) lenr[j] = lenr[j+1] + (p[j]=='*'?0:1);
            for(int j=1;j<=M;j++) lenl[j] = lenl[j-1] + (p[j-1]=='*'?0:1);
            
            unordered_set<int> F{0}, G;
            for(int i=0;i<=N;i++) G.insert(i);
            
            for(int j=1;j<=M;j++) {
                unordered_set<int> nF,nG;
                for(int i=lenl[j];i<=N-lenr[j];i++) {
                    if( i > 0 && (p[j-1] == '?' || s[i-1]==p[j-1]) && F.count(i-1) )
                        nF.insert(i);
                    if( p[j-1] == '*' && G.count(i))
                        nF.insert(i);
                    if( nG.count(i-1) || nF.count(i) ) 
                        nG.insert(i);
                }
                F = nF;
                G = nG;
            }
            return F.count(N);
        }
    };

Log in to reply
 

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