My solution with 6ms runtime:

bool match(int i,int j,string &p,string &s,vector<vector<int> >&dp) { if(i==p.size()&&j==s.size()) return true; int &ans=dp[i][j]; if(ans!=-1) return dp[i][j]; if(j==s.size()) { if((i+2)<=p.size()&&p[i+1]=='*') return dp[i][j]=match(i+2,j,p,s,dp); else return false; } if((i+1)<p.size()&&p[i+1]=='*') { if(p[i]=='.'||p[i]==s[j]) return ans=(match(i,j+1,p,s,dp)||match(i+2,j,p,s,dp)||match(i+2,j+1,p,s,dp)); else return ans=match(i+2,j,p,s,dp); } if(p[i]=='.'||p[i]==s[j]) return ans=match(i+1,j+1,p,s,dp); return ans=false; } bool isMatch(string s, string p) { int n=p.size(),m=s.size(); vector<vector<int> >dp(n+1,vector<int>(m+1,-1)); return match(0,0,p,s,dp); }Regular Expression Matching