【★】有效的括号字符串 checkValidString

解法思路：

代码如下：

class Solution {
    // 采用贪心算法
    public boolean checkValidString(String s) {
        int low = 0, up = 0;//记录到目前的位置时存在的左括号的最少的数量和最大的数量
        for(int i = 0; i < s.length(); i++){
            char tmp = s.charAt(i);
            if(tmp == '('){
                low++;
                up++;
            }else if(tmp == '*'){
                low = Math.max(0, low - 1);
                up++;
            }else{
                low = Math.max(low - 1, 0);
                up--;
                if(up < 0) return false;
            }
        }
        return low <= 0;
    }
}

运行结果截图如下：