NC175 合法的括号字符串

import java.util.*;


public class Solution {
    public boolean isValidString (String s) {
        //创建两个linkedList(是基于双向链表实现的)，new LinkedList<>();
        //ArrayList是基于数组实现的，动态分配内存
        LinkedList<Integer> left=new LinkedList<>();
        LinkedList<Integer> star=new LinkedList<>(); 
        int n=s.length();
        //设置两个栈，left和star
        //遍历字符串，用字符串s名.charAt(i)，定位到字符串s的第i位，获得字符串s第i位的字符
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            //如果是左括号和星号就入栈
            if(c=='('){
                left.push(i);
            }else if(c=='*'){
                star.push(i);
            }else{
                //如果是右括号，就先将它与左括号进行匹配，如果没有左括号再与星号匹配（此时星号作为左括号），这样如果能找到与所有的右括号进行匹配，就表示右括号匹配成功
                if(!left.isEmpty()){
                    left.pop();
                }else if(!star.isEmpty()){
                    star.pop();
                }else{
                    return false;
                }
            }
        }
        //再将剩下的左括号和星号进行匹配，此时星号作为右括号或就是空格
        //只要两个栈不为空，就将栈顶元素弹出，由于左括号对应的ACSII比*对应的ACSII小，所以如果top1>top2，就表明匹配不成功
        while(!left.isEmpty()&&!star.isEmpty()){
            int top1=left.pop();
            int top2=star.pop();
            if(top1>top2){
                return false;
            }
          
        }
        //最后只需要去判断一下左括号栈是否为空，如果左括号栈为空，就表明所有的左括号都匹配成功，就算有剩下的*也没事，因为这些剩下的*就是作为空格
            return left.isEmpty();
    }
}