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

使用两个栈，一个存放左括号，一个存放*，如果碰到右括号，先和左括号栈里的进行抵消，如果左括号栈为空再和*栈的抵消。最后再判断左括号栈长度是否小于等于*栈，满足的话说明剩余的左括号也都可以抵消，但是这样忽略了左括号和*的有效作用区间，也就是入栈时间，比如**((),最后虽然*栈长度大于左括号栈，但是那些*是在左括号之前的，无法与左括号进行抵消。

因此还需要两个栈来分别计算左括号栈和*栈中数据的入栈时间（可以用在数组中的index），它们与左括号栈和*栈同时进行push(),pop()操作。

最后遍历两个时间栈，如果存在左括号的时间>*的时间，说明不合法返回false。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        // write code here
        char[] str = s.toCharArray();
        // 存放左括号
        Deque<Character> stack = new LinkedList<>();
        // 记录左括号栈里的左括号入栈时间
        Deque<Integer> stackNum = new LinkedList<>();
        // 存放*号
        Deque<Character> stack2 = new LinkedList<>();
        // 记录*栈中 *的入栈时间
        Deque<Integer> stackNum2 = new LinkedList<>();
        for(int i = 0;i<str.length;i++){
            if(str[i] == '('){
                stack.push(str[i]);
                stackNum.push(i);
            }else if(str[i] == '*'){
                stack2.push(str[i]);
                stackNum2.push(i);
            }else{ // 如果遇到右括号
                // 先判断 stack是否为空
                if(!stack.isEmpty()){
                    stack.pop();
                    stackNum.pop();
                }else{
                    if(stack2.isEmpty()){
                        return false;
                    }else{
                        stack2.pop();
                        stackNum2.pop();
                    }
                }
            }
        }
        
        while(!stack.isEmpty() && !stack2.isEmpty()){
            // 如果左括号入栈时间比*晚 返回false
            // 因为即使有* 但是它无法作用到后面的左括号 比如 **( 就是不合法的
            if(stackNum.pop() > stackNum2.pop())
                return false;
            stack.pop();
            stack2.pop();
        }
        return stack.isEmpty();
    }
}