LeetCode 678. 有效的括号字符串 括号序列+栈

题目链接

class Solution {
public:
    bool checkValidString(string s) {
        stack<int>st;
        stack<int>st1;
        int len=s.size();
        for(int i=0;i<len;i++){
            if(s[i]=='(')
                st.push(i);
            else if(s[i]=='*')
                st1.push(i);
            else{
                if(st.size())
                    st.pop();
                else{
                    if(st1.size()) st1.pop();
                    else return false;
                }
            }
        }
        while(st.size()){
            if(st1.size()&&st1.top()>st.top())
                st1.pop(),st.pop();
            else return false;
        }
        return true;
    }
};

class Solution {
public:
    bool checkValidString(string s) {
        int low = 0, high = 0;
        for (auto c: s) {
            if (c == '(') low ++, high ++ ;
            else if (c == ')') low -- , high -- ;
            else low --, high ++ ;
            low = max(low, 0);
            if (low > high) return false;
        }
        return !low;
    }
};