678. Valid Parenthesis String

Description

Solution

Using a list to store the availiable number of * scaned forward. If we meet a ‘)’ and there is no ‘(‘ in the stack, then we gonna use * to match.

As for mismatched ‘(‘, we should use * following to match it.

Code

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> stk;
        vector<int> count(s.size()+1, 0);
        for(int i = 0; i < s.size(); i++){
            count[i+1] = count[i];
            if(s[i] == '(')
                stk.push(i);
            else if(s[i] == '*')
                count[i+1]+=1;
            else{
                if(stk.empty() && !count[i+1])
                    return false;
                if(!stk.empty())    
                    stk.pop();
                else
                    count[i+1]-=1;
            }
        }
        while(!stk.empty()){
            auto top = stk.top(); stk.pop();
            if(count[s.size()] - count[top + 1] <= 0)
                return false;
            count[s.size()]--;
        }
        return true;
    }
};