合法的括号字符串

牛客链接：NC175 合法的括号字符串

解法1：栈

我们使用两个栈来保存left和star的位置，每次匹配到右括号，首先在left中寻找最先出现的左括号进行匹配，若不存在，则去star中寻找星号进行匹配。
当右括号多的时候，则为false；
当右括号匹配完毕，左括号和星号进行匹配，此时星号要求数量大于左括号（星号可以为空），并且相应的每个星号要在左括号的右边才能匹配成功。否则都应为false。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */
    bool isValidString(string s) {
   
        // write code here
        stack<int> left;
        stack<int> star;
        for(int i = 0; i<s.size();++i){
   
            if(s[i] == '(')
                left.push(i);
            else if(s[i] == '*')
                star.push(i);
            else if(s[i] == ')')
            {
   
                if(left.size()>0)
                    left.pop();
                else if(star.size()>0)
                    star.pop();
                else
                    return false;
            }
        }
        if (left.size()>star.size())    //星号要求数量大于左括号
            return false;
        
        if(left.size()>0 && left.size()<=star.size())  //一次匹配左括号
            while(left.size()>0)
                if(left.top()>star.top())
                    return false;
                else{
   
                    left.pop();
                    star.pop();
                }
        
        return true;
    }
};

解法2：贪心

首先从左到右，将所有看做(，进行计数。如果出现右括号数量大于左括号的数量，则必不合法；
反之，从右到左，将都看做)，进行计数。如果出现左括号大于右括号数量，则不合法。
剩余情况，可以将多余的括号变为空格。即合法。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */
    bool isValidString(string s) {
   
        // write code here
        int left = 0, right = 0;
        for(int i =0;i<s.size();++i) //*视为(
        {
   
            if(s[i] == '(' or s[i] == '*')
                ++left;
            else{
   
                ++right;
                if(right>left)
                    return false;
            }
                
        }
        left = right = 0;
        for(int i =s.size()-1;i>=0;--i) //*视为(
        {
   
            if(s[i] == ')' or s[i] == '*')
                ++right;
            else{
   
                ++left;
                if(left>right)
                    return false;
            }
                
        }
        return true;
        
    }
};