题目描述

难度：中等

给定一个只包含三种字符的字符串：（，）和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

字符串大小将在 [1，100] 范围内。

分析

仔细读题后结合示例分析，简而言之就是左右括号必须在顺序上保持正确，并且在拥有星号的前提下，左右括号必须匹配完整，不能有多余的一方出现；
理清题目思绪后，我们可以利用栈来解决这道题；

先声明两个栈，一个放左括号下标，一个放星号下标；其中主要原理就是所有遍历字符串的时候，将所有碰到的左括号、星号的下标入栈，碰到右括号就去左括号栈中弹出一个左括号下标，用来匹配；如果此时左括号栈中为空，那么就去星号栈弹出一个元素用来匹配；如果两个栈都为空，那么说明右括号没有与之匹配的元素，返回 false；

当字符串遍历完成之后，如果此时左括号栈中还有元素，那么就用星号栈中的星号与之匹配，唯一的 fasle 条件就是当星号栈弹出的索引小于左括号栈弹出的索引，出现这种情况时星号出现的位置在左括号左边，违背的顺序原则（要想返回 true，星号栈中弹出的元素必须大于左括号栈中弹出的元素）。

代码：

 public boolean checkValidString(String s) {

        Stack<Integer> leftStack = new Stack<>();  // 左括号栈
        Stack<Integer> starStack = new Stack<>();  // 星号栈

        // 从头遍历字符串 遇到左括号入栈 遇到星号入栈 遇到右括号优先左括号元素出栈 其次星号出栈
        for (int i = 0; i < s.length(); i++) {
            char item = s.charAt(i);
            if(item == '('){
                leftStack.push(i);
            }else if(item == '*'){
                starStack.push(i);
            }else {
                if(!leftStack.empty()){
                    leftStack.pop();
                }else if(!starStack.empty()){
                    starStack.pop();
                }else {
                    return false;
                }
            }
        }

        // 字符串遍历完之后
        while (!leftStack.empty() && !starStack.empty()){
            if(leftStack.pop() > starStack.pop()) {  // 最右边的左括号的下标大于最右边的星号下标 代表有一个左括号没有匹配 返回false
                return false;
            }
        }

        return leftStack.empty();
    }