用两个栈stk_l和stk_s分别记录当前未抵消的左括号’(‘和’*’的位置。
stk_s中的星号两种抵消方式
1. 左括号不够用来抵消当前的右括号,这时用stk_s中存的星号来抵消
2. 字符串遍历完后,stk_l 中剩余的左括号需要用在这些左括号右边的星号抵消
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
stack<int> stk_l, stk_s;
for (int i = 0; i<n; i++){
char &c = s[i];
if (c == '(')
stk_l.push(i);
else if (c == '*')
stk_s.push(i);
else if (c == ')'){
if (stk_l.size()) stk_l.pop();
else{
if (stk_s.size()) stk_s.pop();
else
return false;
}
}
}
while (stk_l.size()){
if (stk_s.size() && stk_s.top() > stk_l.top())
stk_s.pop(), stk_l.pop();
else return false;
}
return true;
}
};