eetodealidarenthesistringoodle

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Example 1:

Example 2:

Example 3:

Constraints:

有效的括号字符串。

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

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

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

首先是扫描两遍的做法。第一遍从左往右，第二遍从右往左。第一遍扫描的时候，把星号当做左括号，所以遇到左括号和星号的时候就 left++，遇到右括号就 left--；过程中只要 left 小于 0 就 return false，说明右括号多而且是星号没法补救的。第一遍扫描完毕之后如果 left == 0 则直接 return true，因为左括号 + 星号可以和右括号互相抵消。如果 left 大于0 也不用担心，因为这里面应该是存在一些星号的。

第二遍扫描的时候是从右往左，此时把星号当做右括号，如果看到右括号或者星号就 right++，看到左括号就 right--；跟第一遍一样，过程中只要 right 小于 0 了就 return false，说明左括号多到无法补救。遍历结束则 return true。

一个疑问：如果第一遍里面只是左括号比较多，left 不也是大于 0 吗？没问题，第二遍扫描的时候，这种 case 会被抓出来（因为 right 会小于 0 了）从而 return false。

空间O(1)

Java实现

JavaScript实现

接下来是扫描一遍的做法。这里我们设置两个变量cmax和cmin，代表需要被match的左括号的上限和下限。

当遇到一个左括号的时候，cmax和cmin都需要++，因为你需要为这个左括号找一个配对

当遇到一个右括号的时候，自然是cmax--，cmin也需要--，但是如果cmin小于0了，说明右括号更多了，此时我们为了不让他小于0，我们取的是0和cmin的较大值

当遇到一个星号的时候，因为他是通配符，所以如果当做左括号的话，cmax就++，如果当做右括号的话，cmin就--，因为他可以去抵消一个左括号

最后判断的时候，如果cmax小于0就return false，因为cmax只有在遇到右括号的时候才--，说明右括号多到无法被抵消。

空间O(1)

Java实现

第三种解法用到栈。这里我们需要两个栈，一个记录左括号的 index，一个记录星号的 index，这里我们分别叫做 stack1 和 stack2。

此时我们可以处理所有左括号，但是 stack1 和 stack2 可能不为空，此时我们需要判断 stack2 里面的星号是否能抵消 stack1 里剩余未配对的括号。注意这里配对的原则是如果括号的 index 大于星号的 index，说明这个括号是不能被抵消的，因为他出现在了一个星号之后，星号只能抵消之前的括号。