0ms o(n)-space c solution using dp


  • 1
    T
    bool isMatch(char* s, char* p) {
        const int SLEN = strlen(s);
        bool matchs[SLEN+1];
        memset(matchs, 0, sizeof(matchs));
        matchs[0] = true;
        while(p[0] != '\0'){
            if('*' == p[1]){
                for(int i = 0; i <= SLEN; ++i)
                    if(!matchs[i] && i!=0 && matchs[i-1] && ('.' == p[0] || p[0] == s[i-1])) 
                        matchs[i] = true;
                p = p + 2;
            }else{
                for(int i = SLEN; i >=0; --i)
                    if(i!=0 && matchs[i-1] && ('.' == p[0] || p[0] == s[i-1]))  matchs[i] = true;
                    else matchs[i] = false;
                ++p;
            }
        }
        return matchs[SLEN];
    }

  • 0
    T

    4ms c++ version:

    bool isMatch(string& s, string& p) {
            const int SLEN = s.length();
            const int PLEN = p.length();
            bool matchs[SLEN+1];
            memset(matchs, 0, sizeof(matchs));
            matchs[0] = true;
            for(int j = 0; j < PLEN; ++j){
                if(j+1 < PLEN && '*' == p[j+1]){
                    for(int i = 0; i <= SLEN; ++i)
                        if(!matchs[i] && i!=0 && matchs[i-1] && ('.' == p[j] || p[j] == s[i-1])) 
                                 matchs[i] = true;
                    ++j;
                }else{
                    for(int i = SLEN; i >=0; --i)
                        if(i!=0 && matchs[i-1] && ('.' == p[j] || p[j] == s[i-1]))  matchs[i] = true;
                        else matchs[i] = false;
                }
            }
            return matchs[SLEN];
        }

  • 0
    T

    72ms python version:

    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            SLEN,PLEN,j = len(s), len(p), 0
            matchs = [False] * (SLEN + 1);
            matchs[0] = True;
            while j < PLEN:
                if j+1 < PLEN and '*' == p[j+1]:
                    for i in xrange(SLEN+1):
                        if not matchs[i] and i != 0 and matchs[i-1] and ('.' == p[j] or p[j] == s[i-1]): 
                                 matchs[i] = True;
                    j+=2
                else:
                    for i in xrange(SLEN, -1, -1):
                        if i != 0 and matchs[i-1] and ('.' == p[j] or p[j] == s[i-1]):  matchs[i] = True;
                        else: matchs[i] = False;
                    j+=1
            return matchs[SLEN];

Log in to reply
 

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