678. Valid Parenthesis String

Solution 1. Use stacks. Storing the index of each char.
    bool checkValidString(string s) {
        stack<int> st;
        stack<int> blk;
        for(int i=0; i<s.size(); i++) {
            char c = s[i];
            if(c == '(') st.push(i);
            else if(c == '*') blk.push(i);
            else {
                if(st.empty() && blk.empty()) return false;
                if(!st.empty()) st.pop();
                else blk.pop();
            }
        }
        if(st.size()>blk.size()) return false;
        while(!st.empty() && !blk.empty()) {
            if(blk.top()<st.top()) return false;
            st.pop();
            blk.pop();
        }
        return st.empty();
    }
Solution 2. Counting the remaining '(' at each step.
    bool check(string& s, int i=0, int cnt=0) {
        if(cnt < 0) return false;
        if(i==s.size()) return cnt == 0;
        if(s[i] == '(') return check(s, i+1, cnt+1);
        else if(s[i] == ')') return check(s, i+1, cnt-1);
        else return check(s, i+1, cnt)
            || check(s, i+1, cnt+1)
            || check(s, i+1, cnt-1);
    }
    bool checkValidString(string s) {
        return check(s);
    }