推 sustainer123: 這題我偷看溫莎才想出來 沒考慮到index問題 04/07 21:31
推 wu10200512: 這題跟跟可替代回文串差不多的感覺 04/07 21:41
→ digua: 大師 04/07 21:41
→ oinishere: 可替代回文串有題目ㄇ 我好像沒寫過 04/07 21:44
題目：
( ) 匹配問題
只是多了一個*可以變成( )或是空的東西
直接舉例
(***
*()*
(***)
都是合法的
解法：
先把右括號通通弄掉
然後剩下的左掛號跟*號用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;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.47.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712496161.A.CCB.html