算法---LeetCode 678. 有效的括号字符串

1. 题目

原题链接

给你一个只包含三种字符的字符串，支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。

有效 字符串符合如下规则：

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

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “(*)”
输出：true
示例 3：

输入：s = “(*))”
输出：true

提示：

1 <= s.length <= 100
s[i] 为 ‘(’、‘)’ 或 ‘*’

2. 题解

2.1 解法1: 两个栈

两个栈记录目前为止不能匹配的字符，也就是*和(，每次出现右括号我们就应该去两个栈匹配可以匹配的左括号。

而*可以作为任何括号，也可以作为空字符串，所以我们应该优先用左括号匹配，所以我们出栈的策略如下：

1. 遇到左括号，直接进栈，记录括号的位置。
2. 遇到星号，直接进栈，记录星号的位置。
3. 遇到右括号：
   a: 左括号栈里有元素，直接出栈。
   b: 左括号栈里无元素，*栈里有元素，直接出栈。无元素的话就已经匹配失败了。

如果遍历完数组的话，我们可能会发现左括号栈里还有结余元素。如果是20题的情况，已经失败了。但现在我们可能还有一些星号可以作为右括号用，所以我们进行下面的匹配操作：

对左括号栈逐一出栈，然后去看此时星号栈的栈顶，如果栈顶元素的位置大于左括号栈顶元素的位置，说明星号在括号的右侧，可以匹配。否则不可。

classSolution{publicbooleancheckValidString(Strings){Deque<Integer>star=newLinkedList<>();Deque<Integer>left=newLinkedList<>();for(inti=0;i<s.length();i++){charc=s.charAt(i);if(c=='('){left.offerLast(i);}elseif(c=='*'){star.offerLast(i);}elseif(!left.isEmpty()){left.pollLast();}elseif(!star.isEmpty()){star.pollLast();}else{returnfalse;}}while(!left.isEmpty()&&!star.isEmpty()){if(left.pollLast()>star.pollLast()){returnfalse;}}returnleft.isEmpty();}}

参考:
【微扰理论】肯定是栈呀）