String-678-Valid Parenthesis String
2018-02-12 14:59:08         来源：MayUWell

Description:
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].

Solution:

```/*
*贪心算法。lo表示可能的最少的'('数，hi表示可能的最多的'('数。符合的条件为lo<=0并且hi>=0.
*因此每轮迭代lo取Math.max(lo,0),并且当hi<0(表示左括号最多也不会多于0个)可以直接退出循环。
*退出循环后判断lo是否等于0即可
*/
class Solution {
public boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (char c: s.toCharArray()) {
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
if (hi < 0) break;
lo = Math.max(lo, 0);
}
return lo == 0;
}
}```