class Solution {
public:
bool isMatch(string s, string p) {
int n = (int)s.size(), m = (int)p.size();
bool f[2*n+2], *f1=f, *f2=f+n+1;
fill_n(f, 2*n+2, false);
f1[n]=true;
bool star = false;
for (int j = m1; j >= 0; j) {
if (p[j]=='*') {
star = true;
continue;
} else {
if (!star) {
f2[n]=false;
for (int i = n1; i >= 0; i) {
if (s[i] == p[j]  (p[j] == '.'))
f2[i] = f1[i+1];
else
f2[i] = false;
}
} else {
f2[n]=f1[n];
for (int i = n1; i >= 0; i) {
int k = i;
f2[i] = false;
while (k < n && (s[k] == p[j]  p[j] == '.')) {
if (f1[k]) {
f2[i] = true;
break;
}
k++;
}
if (!f2[i])
f2[i]=f1[k];
}
}
star = false;
}
swap(f1, f2);
}
return f1[0];
}
};
Accepted 4ms C++ dynamic programming with O(n) space


I would say just more practice. You understand O(n^2) DP version, then you will notice that you are working on the n^2 table row by row, and the current row only depends on the previous row. Now you know that this can be done with O(n) version. A bit tricky is that when the last row corresponds to '*', the current row depends on the row before the last row. Let me know if you need any further assistance.

I see, you use extra loop to the row before the last row. Yes, I notice that each row i depends only itself, row i1, and row i2. In my implementation I just build 3 rows to store the information, instead of extra looping. The code is also linear space and 4ms. BTW, it seems to me that you do the matching backward, why is that? What's the gain?

Another cleaner implementation with half space needed
bool isMatch(string s, string p) { int ns = (int)s.size(), np = (int)p.size(); bool f[ns+1]; fill_n(f, ns+1, false); f[ns]=true; bool star=false; for (int j = np1; j >= 0; j) { if (p[j]=='*') { star=true; continue; } if (!star) { for (int i = 0; i < ns; i++) { if (p[j]=='.'  s[i]==p[j]) f[i]=f[i+1]; else f[i]=false; } f[ns]=false; } else { for (int i = 0; i < ns; i++) { if (f[i]) continue; for (int k = i; k < ns; k++) { if (p[j]=='.'  s[k]==p[j]) { if (f[k+1]) f[i]=true; } else break; } } } star=false; } return f[0]; }