C++算法集锦：字符串操作

• 合法的括号字符串

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

解法1：栈

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

class Solution {
public:
    
    bool isValidString(string s) {
        // write code here
        stack left;
        stack star;
        for(int i = 0; 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:
    
    bool isValidString(string s) {
        // write code here
        int left = 0, right = 0;
        for(int i =0;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;
        
    }
};