用两个栈分别存放左括号与星号的下标。

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> left, star;

        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] == '(') left.push(i);              //left栈存左括号下标
            else if (s[i] == '*') star.push(i);         //star栈存星号下标
            else
            {
                if (left.size()) left.pop();            //用左括号匹配右括号
                else if (star.size()) star.pop();       //用星号匹配右括号
                else return false;                      //没有左括号或星号能匹配右括号
            }
        }                                               //至此，右括号已经全被匹配消除

        while (left.size() && star.size())              //将剩余的左括号与星号两两匹配消除
        {
            if (left.top() > star.top()) return false;  //若左括号下标大于星号，
            else left.pop(), star.pop();                //即星号无法充当右括号进行匹配，返回false
        }

        if (left.size()) return false;    //若左括号还有剩余，说明星号不能完全匹配掉左括号

        return true;
    }
};

参考文献

借助双栈解题