# Accelerating DP in C++, without explanation

• ``````class Solution {
public:
bool isMatch(string s, string p) {
int sLen = s.length(), pLen = p.length();
bool **match = new bool*[sLen+1];
for(int i = 0; i <= sLen; i++) match[i] = new bool[pLen+1]();
match[0][0] = true;
for(int i = 1; i <= pLen; ++i)
if(p[i-1] == '*') match[0][i] = true; else break;
for(int i = 1; i <= sLen; ++i){
for(int j = 1; j <= pLen; ++j) {
if(p[j-1] == '*') match[i][j] = match[i-1][j] || match[i][j-1];
else match[i][j] = (s[i-1]==p[j-1] || p[j-1]=='?') && match[i-1][j-1];
}
}
bool ret = match[sLen][pLen];
for(int i = 0; i <= sLen; ++i) delete [] match[i];
delete [] match;
return ret;
}
};
``````

The normal DP solution above will cost 500ms. But if we eliminate some corner cases - counting the `*` as follows, it will be accelerated to 60ms.

``````        int count = 0;
for(int i = 0; i < pLen; i++) if(p[i] == '*') count++;
if((count==0 && pLen!=sLen) || (pLen-count>sLen)) return false;
``````

More optimised solutions using DP costing 28ms are :

``````bool isMatch(string s, string p) {
int sLen = s.length(), pLen = p.length();
int match[sLen+1]{0};
match[0] = 1;
for(int i = 0; i < pLen; ++i) {
if(p[i] == '*') {
for(int j = 1; j <= sLen; ++j)
match[j] = match[j-1] || match[j];
}
else {
int t0, t1 = match[0];
for(int j = 1; j <= sLen; ++j) {
t0 = match[j];
match[j] = t1 && (p[i]=='?' || p[i]==s[j-1]);
t1 = t0;
}
match[0] = 0;
}
}
bool ret = match[sLen];
delete [] match;
return ret;
}
``````

More terse version:

``````bool isMatch(string s, string p) {
int sLen = s.length(), pLen = p.length();
int count = 0;
for(int i = 0; i < pLen; i++) if(p[i] == '*') count++;
if((count==0 && pLen!=sLen) || (pLen-count>sLen)) return false;
int *match = new int[sLen+1]();
match[0] = 1;
for(int i = 0; i < pLen; ++i) {
if(p[i] == '*') {
for(int j = 1; j <= sLen; ++j) match[j] = match[j-1] || match[j];
}
else {
for(int i = sLen; j > 0; --j)
match[j] = match[j-1] && (p[i]=='?' || p[i]==s[j-1]);
match[0] = 0;
}
}
bool ret = match[sLen];
delete [] match;
return ret;
}
``````

The legendary iterative solution, not a DP but efficient.

``````bool isMatch(string s, string p) {
int sIndex=0, pIndex=0;
int sAIndex=-1, pAIndex=-1;
int sLen=s.length(), pLen=p.length();
while(sIndex < sLen) {
if(s[sIndex]==p[pIndex] || p[pIndex]=='?') { sIndex++, pIndex++; continue;  }
if(p[pIndex] == '*') { pAIndex = pIndex++; sAIndex = sIndex; continue;  }
if(pAIndex > -1) { pIndex = pAIndex+1; sIndex = ++sAIndex; continue;  }
return false;
}
while(p[pIndex] == '*') pIndex++;
return pIndex==pLen;
}``````

• @LHearen Do you have any idea, why my submissions were not there as usual, `not found in the server` Weird!!!

• @Salkexy2 Sorry about that, the server sometimes crashed for the high frequent retrieving and visiting. Sorry about that. @1337c0d3r I think we will do better to further avoid this case.

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