[LeetCode] 678. Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

The string size will be in the range [1, 100].

有效的括号字符串。

题意是给一个字符串，里面有左括号右括号和星号，请判断input是否是一个合法的括号组合。其中星号是一个wildcard，可以表示左括号右括号或者星号。做这个题之前需要先复习一下20题。这道题我提供两种做法，第一种扫描两遍，第二种扫描一遍。

首先是扫描两遍的做法。第一遍从左往右，第二遍从右往左。第一遍扫描的时候，把星号当做左括号，所以遇到左括号和星号的时候就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(n)

空间O(1)

Java实现

 1 class Solution {
 2     public boolean checkValidString(String s) {
 3         int left = 0;
 4         int right = 0;
 5         int n = s.length();
 6         // scan from left to right
 7         for (int i = 0; i < n; i++) {
 8             if (s.charAt(i) == '(' || s.charAt(i) == '*') {
 9                 left++;
10             } else {
11                 left--;
12             }
13             if (left < 0) {
14                 return false;
15             }
16         }
17         if (left == 0) {
18             return true;
19         }
20 
21         // scan from right to left
22         for (int i = n - 1; i >= 0; i--) {
23             if (s.charAt(i) == ')' || s.charAt(i) == '*') {
24                 right++;
25             } else {
26                 right--;
27             }
28             if (right < 0) {
29                 return false;
30             }
31         }
32         return true;
33     }
34 }

JavaScript实现

 1 /**
 2  * @param {string} s
 3  * @return {boolean}
 4  */
 5 var checkValidString = function(s) {
 6     let left = 0;
 7     let right = 0;
 8     let len = s.length;
 9     for (let i = 0; i < len; i++) {
10         if (s.charAt(i) == '(' || s.charAt(i) == '*') {
11             left++;
12         } else {
13             left--;
14         }
15         if (left < 0) {
16             return false;
17         }
18     }
19     if (left == 0) {
20         return true;
21     }
22 
23     for (let i = len - 1; i >= 0; i--) {
24         if (s.charAt(i) == ')' || s.charAt(i) == '*') {
25             right++;
26         } else {
27             right--;
28         }
29         if (right < 0) {
30             return false;
31         }
32     }
33     return true;
34 };

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

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

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

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

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

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public boolean checkValidString(String s) {
 3         int cmin = 0;
 4         int cmax = 0;
 5         for (int i = 0; i < s.length(); i++) {
 6             char c = s.charAt(i);
 7             if (c == '(') {
 8                 cmax++;
 9                 cmin++;
10             } else if (c == ')') {
11                 cmax--;
12                 cmin = Math.max(cmin - 1, 0);
13             } else {
14                 cmax++;
15                 cmin = Math.max(cmin - 1, 0);
16             }
17             if (cmax < 0) {
18                 return false;
19             }
20         }
21         return cmin == 0;
22     }
23 }