1、题目描述

给定一个字符串s，字符串s只包含以下三种完等:(,*,)，请你判断s是不是一个合法的括号字符串。合法括号字符串有如下规则：

1.左括号（必须有对应的右括号)

2.右括号）必须有对应的左括号(

3.左括号必须在对应的右括号前面

4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符

5.空字符串也视为合法的括号字符串。

数据范围： $1\le s.length\le 100$

输入1：
()()
输出1：
true
输入2：
(*)
输出2：
true

2、解题思路

使用两个栈，一个星号栈，一个左括号栈
1、然后遍历整个字符串

碰到左括号，入左括号栈
碰到星号，入星号栈
碰到右括号，优先在左括号栈出栈一个左括号与之匹配，若左括号栈为空，则在星号栈出栈一个*充当左括号与之匹配。
若碰到右括号且此时左括号栈和星号栈都为空，则直接返回false。

2、遍历完成之后，左括号栈和星号栈可能会有剩余，还需要判断
while (!leftStack.isEmpty() && !asterisStack.isEmpty())，当左括号栈和星号栈都有剩余，那步骤如下：

左括号出栈(我们栈里面存的是左括号的下标)
右括号栈出栈(栈里面存的是星号的下标)
比较左括号下标和星号的下标(此时星号充当右括号)， if (leftIndex > asteriskIndex)，则直接return false。

3、在经历过上边两个步骤之后，若左括号栈还有剩余，直接返回false，否则返回true。

3、代码实现

public class LeetCode678 {
    public static boolean checkValidString(String s) {
        Deque<Integer> leftStack = new LinkedList<>();    //左括号栈
        Deque<Integer> asterisStack = new LinkedList<>(); //星号栈
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftStack.push(i);  //碰到左括号，入左括号栈
            } else if (c == '*') {   //碰到星号栈
                asterisStack.push(i);
            } else {  //碰到右括号
                if (!leftStack.isEmpty()) {//如果左括号不为空，左括号栈顶元素出栈
                    leftStack.pop();
                } else if (!asterisStack.isEmpty()) {  //如果左括号栈为空，则从星号栈出栈
                    asterisStack.pop();
                } else {  //左括号栈和星号栈都为空，这时候碰到了右括号，则直接返回false
                    return false;
                }
            }
        }
        //遍历完成之后，若左括号栈和星号栈都有剩余
        while (!leftStack.isEmpty() && !asterisStack.isEmpty()) {
            //左括号栈和星号栈的元素对应出栈
            int leftIndex = leftStack.pop();
            int asteriskIndex = asterisStack.pop();
            //这个时候星号栈的元素就充当右括号，且右括号的下标必须大于左括号，否则直接false
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
        //如果最后左括号栈为空，返回true,星号栈无所谓，因为可以当作空字符串对待
        return leftStack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(checkValidString("()"));
        System.out.println(checkValidString("(*)"));
        System.out.println(checkValidString("(*))"));
        System.out.println(checkValidString("()*))"));
    }
}