```
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<int>> dp(p.size()+1,vector<int>(s.size()+1,0));
//to ensure the border value
//attention please that a substring may be matched with a empty string because of '*'
for(int tp = 1;tp<p.size()+1;tp++)
{
if(p[tp-1]!='*')
{
break;
}
dp[tp][0]=1;
}
for(int tp = 1;tp<s.size()+1;tp++)
{
if(s[tp-1]!='*')
{
break;
}
dp[0][tp]=1;
}
dp[0][0] = 1;
for(int i=1;i<p.size()+1;i++)
{
for(int j=1;j<s.size()+1;j++)
{
if(dp[i-1][j-1]) //match
{
if(s[j-1]==p[i-1]||p[i-1]=='?'||p[i-1]=='*')
{
dp[i][j] = 1;
}
}
else //not match
{
if(p[i-1]=='*') //just when p[i-1] is '*', two substring have chance to match
{
if(dp[i-1][j]||dp[i][j-1])
{
dp[i][j]=1;
}
}
}
}
}
return dp[p.size()][s.size()];
}
};
