/*

bool method1(string s, string p)

{

size_t i = 0;

size_t j = 0;

string ss, pp;

bool flag_star = false;

bool ret = true;

while (i < s.size() && j<p.size())

{

//必定能匹配当前字符

if ('?' == p[j])

{

i++;

j++;

flag_star = false;

}

//确定匹配到当前字符

else if (s[i] == p[j])

{

i++;

j++;

flag_star = false;

}

//进入*匹配

//**

//*?

//*

//*a

else if ('*' == p[j])

{

flag_star = true;

//将**转为另外3种情况

while ('*' == p[j])

{

j++;

}

if (j == p.size())

{

ret = true;

return ret;

}

}

else

{

if (flag_star)

{

i++;

if (i == s.size())

{

ret = false;

return ret;

}

}

else

{

ret = false;

return ret;

}

}

}

if (i<s.size())

{

ret = false;

return ret;

}

while (j<p.size())

{

if (p[j] != '*')

{

return false;

}

j++;

}

return ret;

}

/*

bool method2(string s, string p)

{

//p至少需要匹配到的字符长度=p长度-'*'数量

int cnt_star=0;

for (auto& it : p)

{

if (it == '*')

{

cnt_star++;

}

}

if (p.size() - cnt_star > s.size())

return false;

vector<bool> vec_s(s.size() + 1);

vector<vector<bool>> dp(p.size() + 1, vec_s);

dp[0][0] = true;

for (size_t i = 1; i <= p.size(); i++)

{

//设置每次循环的初值，即当星号不出现在首位时，匹配字符串的初值都为false

dp[i][0] = dp[i - 1][0] && p[i - 1] == '*';

}

for (size_t j = 1; j <= s.size(); j++)

{

//第0行p为空，此时没有东西能匹配的上

dp[0][j] = false;

}

for (size_t i = 1; i <= p.size(); i++)

{

for (size_t j = 1; j <= s.size(); j++)

{

if (s[j - 1] == p[i - 1]|| p[i - 1] == '?')

{

dp[i][j] = dp[i - 1][j - 1];

}

else if (p[i-1]=='*')

{

//动态规划递推式（星号） 表示星号可以匹配

//0个（决定于上次外循环的结果）或者

//多个（决定于刚才内循环的结果）

dp[i][j] = dp[i - 1][j] || dp[i][j - 1];

}

}

}

return dp[p.size()][s.size()];

}

bool isMatch(string s, string p)

{

return method2(s, p);

}

{

Solution so;

return so.isMatch(s, p);

}