The shortest AC code.


  • 93
    E

    1.'.' is easy to handle. if p has a '.', it can pass any single character in s except '\0'.

    2.'' is a totally different problem. if p has a '' character, it can pass any length of first-match characters in s including '\0'.

      class Solution {
        public:
        bool matchFirst(const char *s, const char *p){
            return (*p == *s || (*p == '.' && *s != '\0'));
        }
    
    bool isMatch(const char *s, const char *p) {
    	if (*p == '\0') return *s == '\0';	//empty
    
    	if (*(p + 1) != '*') {//without *
    		if(!matchFirst(s,p)) return false;
    		return isMatch(s + 1, p + 1);
    	} else { //next: with a *
        	if(isMatch(s, p + 2)) return true;    //try the length of 0
    		while ( matchFirst(s,p) )       //try all possible lengths 
    			if (isMatch(++s, p + 2))return true;
    	}
    }
    };

  • 0
    J

    What an amazing method!


  • 0
    Z

    Concise and clear!
    just one problem, seems in isMatch(), not all paths has a return value.


  • 0
    I

    So elegant! Could you give a little tips about how you came up with the idea when you're convenient? Thanks


  • 0
    N

    good method! but maybe in the end of "else“, you should "return false;" after try all possible lengths. if you didn't return explicitly, return value maybe different in different platform.


  • 0
    P

    It seems that recursive solution in wildcard matching will result in TLE. But it pass here


  • 0
    C
    This post is deleted!

  • 0
    S

    amazing job!


  • 18
    L

    a shorter one (14 lines of code) with neatly format:

    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            for( char c = *p; c != 0; ++s, c = *p ) {
        		if( *(p+1) != '*' )
        			p++;
        		else if( isMatch( s, p+2 ) )
        			return true;
        		if( (*s==0) || ((c!='.') && (c!=*s)) )
        			return false;
        	}
        	return *s == 0;
        }
    };

  • 0
    J

    This is neat, however, I think DP is better lol


  • 0
    W
    This post is deleted!

  • 7
    W

    Well, here is my DP solution, 19 lines (can be shorter if you want), AC in 56ms:

    class Solution {
    public:
    bool isMatch(const char *s, const char *p) {
        vector<bool> dp{true}, tmp;
        for(const char * pp = p;pp && *pp;++pp)
            dp.push_back('*' == *pp ? *(dp.rbegin() + 1) : false);
        for(const char * ss = s;ss && *ss;++ss, tmp.clear()){
            tmp.push_back(false);
            for(size_t i = 0;i < dp.size() - 1;++i)
                tmp.push_back('.' == p[i] || *ss == p[i] ?
                    dp[i] :
                    ('*' == p[i] ?
                        *(tmp.rbegin() + 1) || (('.' == p[i - 1] || *ss == p[i - 1]) && (tmp.back() || dp[i + 1]))
                        : false));
            dp.swap(tmp);
        }
        return dp.back();
    }
    };
    

    The main idea is that, let T(i, j) denotes whether s[0...i) matches p[0...j), then

    T(i+1, j+1) = 
    case 1: T(i, j), if(s[i] == p[j] || p[j] == '.');   //if S matches P, then Sx matches Px;
    case 2: T(i+1, j) || T(i, j+1), if('*' == p[j] && (s[i] == p[j] || p[j] == '.'));   //if S matches P, then S matches P*; if S matches Px*, then Sx matches Px*
    case 3: T(i+1, j-1), if('*' == p[j] && (s[i] != p[j-1]);   //if S matches P, then S matches Px*
    case 4: false;
    

    T(0, 0) = true.


  • -69
    L

    Actullay this is the real shorted code:

    class Solution:
        # @return a boolean
        def isMatch(self, s, p):
            return re.match('^' + p + '$', s) is not None
    

  • 0
    M

    there's something wrong with the answer, it can't pass in ("ba", "ba")


  • 14
    S

    That's far from shortest dude

    bool isMatch(const char *s, const char *p) {
            if (!*p)
                return !*s;
            if (p[1] == '*')
                return isMatch(s, p+2) || (*p == '.' && *s || *s == *p) && isMatch(s+1, p);
            if (*p == '.')
                return *s && isMatch(s+1, p+1);
            return *s == *p && isMatch(s+1, p+1);
        }

  • 0

    nice solution. but recursion is not fast.


  • 0
    Z

    +1

    "maybe in the end of "else“, you should "return false;" after try all possible lengths. if you didn't return explicitly, return value maybe different in different platform."


  • 0
    S

    the explanation is very clear


  • 0
    J

    I think this is what people should do in industry and this is the REAL thing! No idea why people give you so many downvotes...


  • 0
    M

    maybe input data is too weak?


Log in to reply
 

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