[678. Valid Parenthesis String] C++_Using stack


  • 2

    In the stack, we also store the position information.

    class Solution {
    public:
    bool checkValidString(string s) {
        if(s.empty()) return true;
        stack<pair<char, int> > st;
        stack<pair<char, int> > st2;
        int i = 0;
        for(;i < s.size(); ++i){
            if(s[i] == '*'){
                st2.push({s[i],i});
            }else if(s[i] == '('){
                st.push({s[i],i});
            }else{
                if(!st.empty()){
                    st.pop();
                }else if(!st2.empty()){
                    st2.pop();
                }else{
                    break;
                }
            }
        }
        while(!st.empty() && !st2.empty()){
            auto left = st.top();
            auto star = st2.top();
            if(left.second >= star.second){
                break;
            }
            st.pop();
            st2.pop();
        }
        return st.empty() && i == s.size();
    }
    };

  • 0
    M

    I had quite a similar approach.


  • 0
    L
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.