0模拟中等 LeetCode678. 有效的括号字符串 NC175 合法的括号字符串

0模拟中等 LeetCode678. 有效的括号字符串 NC175 合法的括号字符串

678. 有效的括号字符串

描述

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

• 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  一个空字符串也被视为有效字符串。

分析

模拟方法：
要想字符串合法，就要使每一个括号得到匹配。合法的括号一定是左括号在前，右括号在后，所以优先考虑右括号的匹配情况。首先是遍历字符串，便利的过程中若遇到是右括号，判断在它前面是否有左括号或者星号,如果左括号的栈和星号的栈都是空，说明右括号得不到匹配，返回false。
遍历整个字符串之后，再考虑剩下的左括号，一定要使剩下的左括号得到匹配才能是字符串合法。判断左括号能得到匹配的关键是，左括号的下标一定要在星号的前面，这样星号才能充当右括号，使得左括号得到匹配。

class Solution {public boolean checkValidString(String s) {Stack<Integer> left = new Stack<>();Stack<Integer> star = new Stack<>();for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(ch == '('){left.push(i);}else if(ch == '*'){star.push(i);}else{if(!left.isEmpty()){left.pop();}else if(!star.isEmpty()){star.pop();}else{return false;}}}if(left.size() > star.size()){return false;}while(!left.isEmpty()){int a = left.pop();int b = star.pop();if(a > b){return false;}}return true;}
}