题解 | #合法的括号字符串#

时间复杂度O(N), 空间复杂度O(1)。贪心思想：从左往右遍历，将所有的星号视作左括号，若此时左括号的数目仍然小于右括号，那么一定不成立。相似地再从右往左遍历一遍。最后若不为False, 则说明星号可以自适应转化得到True.

[C++ 代码]

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