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].
判断给出的字符串是否满足以下条件
1.一个左括号必须有一个对应的右括号
2.一个右括号必须有一个对应的左括号
3.左括号必须在其对应的右括号之前
'*'可以作为左括号或者右括号或者空字符串
public boolean checkValidString(String s) {
//本来这道题目是十分简单的，只要遇到( +1，遇到)则 -1,并且每次操作都判断操作数是否大于0即可
//但是因为会含有*号，所以处理方式上会麻烦很多，效率也差，所以下面只给出leetcode推荐算法
/**
* leetcode推荐算法
* When checking whether the string is valid, we only cared about the "balance": the number of extra
* , open left brackets as we parsed through the string
* 当我们判断一个字符串是否合法时，我们只关心他是否"平衡"：即是我们解析字符串得到的额外的左括号的数量
* For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through
* the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the
* first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.
* 比如，'(()())'是合法的，我们逐个解析字符串可以得到1,2,1,2,1,0
* 当我们解析'('的时候我们有1个额外的左括号
* '(('则有两个
* '(()'第二个和第三个左右括号分别抵消，则得到1个左括号，依照这种方法推算下去即可,如果我们计算最后一个字符的结果为0，则表示这个字符串是合法的
* 这表示我们只需要关注计算结果就可以了
* For example, if we have string '(***)', then as we parse each symbol
* , the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*';
* [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.
* 再举个例子'(***)',每个符号的计算结果如下
* '(' ,1
* '(*',因为*可以是任何字符，所以结果可以是 0,1,2
* 同理 '(**' 0, 1, 2, 3
* '(***' 0, 1, 2, 3, 4
* '(***)' 0, 1, 2, 3
* Furthermore, we can prove these states always form a contiguous interval.
* Thus, we only need to know the left and right bounds of this interval.
* That is, we would keep those intermediate states
* described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].
* 此外,我们可以证明这些可能的结果都可以一种连续的区间表示
* 因此，我们只需要左右边界就可以表示可能的结果了
* 对于上面的例子'(***)',我们可以这样表述
* [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].
*/
/**
* lo,hi分别表示最少/最多的左括号数量
*/
int lo = 0,hi = 0;
for(Character c : s.toCharArray()){
//当我们解析当前字符串=='('时,lo+1,hi+1
//当我们解析当前字符串==')'时,左括号被抵消那么 lo-1,hi-1
//当我们解析当前字符串=='*'时,lo表示左括号最少数量所以我们把*当作)处理，lo-1
//hi表示左括号最多数量，则我们把*当作(处理，hi+1
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
//如果hi<0，比如第一个字符就是')'的情况，那么这个字符明显不合法，所以不需要判断直接break
if(hi < 0){
break;
}
//我们允许lo<0的情况，因为lo小于0是*号造成的，比如(********)这种
lo = Math.max(0, lo);
}
//结果由上面的推论可知，只要==0，那么则是合法的
return lo == 0;
}
其实上面算法看起来很玄乎，无外乎就是设定一个最少左括号数，这个数字可以<0,因为你把所有的星号都当成了),但是别忘了星号也可以当成空字符所以用lo = Math.max(0, lo)把星号造成的影响抹去。而最多左括号数在任意时候一定都不能小于0，因为把所有星号都换成(依然抵消不了),再根据规则3可以推断这个字符串一定是不合法的
