有效的括号字符串

心已赠人 2021-09-26 15:12 224阅读 0赞

**问题描述**  
给定一个只包含三种字符的字符串：（ ，） 和 \*，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：  
\-任何左括号 ( 必须有相应的右括号 )。  
\-任何右括号 ) 必须有相应的左括号 ( 。  
\-左括号 ( 必须在对应的右括号之前 )。  
\-\*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。  
\-一个空字符串也被视为有效字符串。

> 例 1:  
> 输入: “()”  
> 输出: True  
> 示例 2:  
> 输入: “(\*)”  
> 输出: True  
> 示例 3:  
> 输入: “(\*))”  
> 输出: True

解题思路：  
利用两个栈，一个存放左括号及索引，一个存放*及索引。每次出现右括号时，首先检查是否存在左括号，存在则左括号出栈，否则，检查是否存在“ \** ” 存在，存在则出栈，否则返回false。最后，判断星号能否代替右括号。根据索引位置来判断。

class Solution {
        public boolean checkValidString(String s) {
           if(s==null||s.length()==0)
                return true;
            Stack<String> left = new Stack<String>();//存放左括号
            Stack<String> star = new Stack<String>();//存放*
            char[] ch = s.toCharArray();
            for (int i = 0; i < ch.length; i++) {
                if(ch[i] == '('){
                    left.push(ch[i]+""+i);
                    continue;
                }
                if(ch[i] == '*'){
                    star.push(ch[i]+""+i);
                    continue;
                }
                if(ch[i] == ')'){
                    if(left.isEmpty()&&star.isEmpty()){
                        return false;
                    }
                    if(!left.isEmpty()){
                        left.pop();
                    }else{
                        star.pop();
                    }
                    continue;
                }
            }
            if(left.size() > star.size()){
                return false;
            }
            //判断其代替左括号的情况
            while(!left.isEmpty()){
                int i_left = Integer.valueOf(left.pop().substring(1));
                int i_star = Integer.valueOf(star.pop().substring(1));
                if(i_left>i_star)
                    return false;
            }
            return true;           
        }
    }