# 4ms o(n)space c++ solution

• The basic idea is to scan through expression p

Use a vector<bool> match to record any substring that match the expression so far. Where match[i] means the first i chars match the expression.

``````class Solution {
public:
bool isMatch(string s, string p) {
vector<bool> match(s.size() + 1, false);
match[0] = true;
bool found;
int a,i;

int maxMatch = 0;
for(a = 0; a < p.size();a++ )
{
//nothing match previous pattern
if(maxMatch < 0) return false;
//match "?*" pattern
if(a+1 < p.size() && p[a+1] == '*')
{
for(i = 0; i <= maxMatch ;i++)
{
if (!match[i]) continue;
else if(i < s.size() && (p[a] == '.' || p[a] == s[i]))
{
match[i+1] = true;
maxMatch = max(maxMatch,i+1);
}

}
a++;
continue;
}
//match single char
found = false;
for(i = maxMatch; i >= 0 ; i--)
{
if (!match[i]) continue;
if (i < s.size() &&(p[a] == '.' || p[a] == s[i]))
{
found = true;
match[i+1] = true;
match[i] = false;
}
else match[i] = false;
}
if(found) maxMatch++;
}
return match.back();
}
};``````

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