# 4ms C++ with DP example annotate, optimised from others.

• ``````class Solution {
public:
/*
for example
s="aab", p="c*a*b"
the DP algorithm: (1 means true, 0 means false)
1)
p   c   *   a   *   b
s
a
a
b

2)
p   c   *   a   *   b
s   1   0   1   0   1   0   <= bits
a
a
b

3)
p   c   *   a   *   b
s   1   0   1   0   1   0   <= bitsPrev
a   0   0   0   1   1   0   <= bits
a
b

4)
p   c   *   a   *   b
s   1   0   1   0   1   0
a   0   0   0   1   1   0   <= bitsPrev
a   0   0   0   0   1   0   <= bits
b

5)
p   c   *   a   *   b
s   1   0   1   0   1   0
a   0   0   0   1   1   0
a   0   0   0   0   1   0   <= bitsPrev
b   0   0   0   0   0   1   <= bits

the result is bits[p.length()]=1.
*/
bool isMatch(string s, string p) {
int plen = p.length();
int slen = s.length();
bool *bits = new bool[plen+1];
bool *bitsPrev = new bool[plen+1];
int i, j;
char sc, pc;
bool *tmp = NULL;

/* initalize the first row bits */
bits[0] = true;
bits[1] = false;
for(i=2; i<plen+1; i++)
{
bits[i] = bits[i-2] && (p[i-1] == '*');
}

/* start from the second row */
for(j=1; j<slen+1; j++)
{
/* set the prev row bits */
tmp = bits; bits = bitsPrev; bitsPrev = tmp;

/* set current char of s */
sc = s[j-1];

/* the first element ought to false */
bits[0] = false;

/* start from the second element */
for(i=1; i<plen+1; i++)
{
/* set current char of p */
pc = p[i-1];

/* fill in the row bits */
if(bitsPrev[i-1] && ((pc == '.') || (pc == sc)))
bits[i] = true;
else if((pc == '*') && (i > 1))  // actually, i won't be 1 here.
bits[i] = bits[i-2] || bits[i-1] || (bitsPrev[i] && (sc == p[i-2] || p[i-2] == '.'));
else
bits[i] = false;
}
}

bool result = bits[p.size()];
delete[] bits;
delete[] bitsPrev;
return result;

}
};``````

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