有效的括号字符串

双栈

一个栈保存左边的括号，一个栈保存号，当遇到右括号时，左括号出栈。
如果是多出来的右括号可以用号消除，如果左括号和号都不能消除，那么一定不能匹配。
如果到最后还有没有匹配的左括号，看看是不是有在左括号右边的号,如果有可以消除一个，否则不匹配

解释视频

class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> left = new ArrayDeque<>(); //放(号的索引
        Deque<Integer> stack = new ArrayDeque<>(); //放*号的索引
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length ; i++) {
            if (chars[i] == '(') {
                left.offerLast(i);
            } else if (chars[i] == '*') {
                stack.offerLast(i);
            } else {
                if (!left.isEmpty()) {
                    left.removeLast();
                } else if (!stack.isEmpty()) {
                    stack.removeLast();
                } else {
                    return false; //两个栈都不能抵消(返回false
                }
            }
        }
        while (!left.isEmpty() && !stack.isEmpty()) {
            if (left.removeLast() > stack.removeLast()) {
                return false; //如果(的索引大于*号的索引，不能构成()
            }
        }
        return left.isEmpty();
    }
}

作者：wang-xue-lei-2
链接：https://leetcode-cn.com/problems/valid-parenthesis-string/solution/1ms-rong-yi-li-jie-de-zhan-pi-pei-by-wan-9ku0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

官方题解思路

赏

谢谢你请我吃糖果

微信