原题链接在这里：
题目：
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].
题解：
计数"("的数目. 遇到"("加一. 遇到")" 减一.
遇到"*". 可能分别对应"(", ")"和empty string 三种情况. 所以计数可能加一, 减一或者不变. 可以记录一个范围[lo, hi].
lo维持在0或以上的位置.
但若是hi都小于0, 说明确定的")"更多, 直接返回false.
否则看最后lo能否能停在0.
Time Complexity: O(s.length()). Space: O(1).
AC Java:
1 class Solution { 2 public boolean checkValidString(String s) { 3 if(s == null || s.length() == 0){ 4 return true; 5 } 6 7 int lo = 0; 8 int hi = 0; 9 for(int i = 0; i