题目：
( ) 匹配问题
只是多了一个*可以变成( )或是空的东西
直接举例
(***
*()*
(***)
都是合法的
解法：
先把右括号通通弄掉
然后剩下的左挂号跟*号用index来比
有剩的话就不行
然后我原本想试试看
用deque代替star的vector
结果写一写把我自己写不明白了
就不爽写了
继续vector
姆咪
class Solution {
public:
bool checkValidString(string s)
{
int len = s.size();
vector<int> star;
int starnow = 0;
int psnow = 0;
int now = 0;
vector<int> paper;
for(int i = 0 ; i < len ; i ++)
{
if((s[i] == '(')||(s[i] == ')'))
{
paper.push_back(i);
}
else if(s[i] == '*')
{
star.push_back(i);
starnow ++;
}
int top = paper.size();
if(paper.size() > 1 && s[paper[top-2]] == '(' && s[paper[top-1]] ==
')')
{
paper.pop_back();
paper.pop_back();
}
else if(paper.size() > 0 && s[paper[top-1]] == ')' && (psnow < star.
size()))
{
paper.pop_back();
psnow ++ ;
}
else if(paper.size() > 0 && s[paper[top-1]] == ')' && (psnow >= star
.size()))
{
return false;
}
}
for(int i = 0 ; i < paper.size() ; i ++)
{
if(s[paper[i]] == ')')return false;
}
for(int i = 0 ; i < paper.size() ; i ++)
{
if(psnow == star.size())
{
return false;
}
while((psnow < star.size())&&(paper[i] > star[psnow]))
{
psnow ++;
if(psnow == star.size())
{
return false;
}
}
psnow ++;
}
// for(int i = 0 ; i < paper.size() ; i ++)
// {
// cout << (paper[i]) << " " ;
// }
// cout << endl ;
// for(int i = 0 ; i < star.size() ; i ++)
// {
// cout << star[i] << " " ;
// }
return true;
}
};