[数据结构与算法]LeetCode 678. 有效的括号字符串

难度：中等

第一次中等题目时间击败100%的用户

解题思路： 以右括号为基准，先把右括号判断完，然后在看看有没有剩下的左括号，在进行左括号与*之间的比较，感觉这题算是一题比较简单的逻辑题，代码如下：

class Solution {
    public boolean checkValidString(String s) {
       if (s.equals("")){
            //如果是空字符串直接返回true
            return true; 
        } 
        
        char[] chars = s.toCharArray();
        int i = 0;  // *的数量
        int a = 0;  // (的数量
        LinkedList<Integer> a1 = new LinkedList<>();  //记录(的位置
        LinkedList<Integer> i1 = new LinkedList<>();  //记录*的位置

        for (int j = 0; j < chars.length; j++) {  
            //该循环以右括号的数量为准，因为右括号必须在左括号的后面
            if (chars[j] == ')'){
                if (a == 0){
                    if (i>0){
                        i -= 1;
                        i1.removeLast();  //删除最近的*的索引
                        continue; //跳过该次循环
                    }
                    return false;
                }
                a -= 1;
                a1.removeLast();  //删除最近的(的索引
                continue; //跳过下面的判断
            }

            if (chars[j] == '('){
                a += 1;
                a1.add(j);
            }

            if (chars[j] == '*'){
                i += 1;
                i1.add(j);
            }
        }

        if (a >0){  //如果左括号还有多余的，就判断左括号的后面是否还有*
            for (int j = 0; j < a; j++) {
                if (i <= 0){  //没有*
                    return false;
                }
                i -= 1;
                Integer iLast = i1.removeLast();
                Integer aLast = a1.removeLast();
                if (aLast>iLast){  //判断*是否在左括号的后面
                    return false;
                }
            }
        }
        return true;
    }
}