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

• 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];
}

• 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];
}

• 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];

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