# [LeetCode] 678. Valid Parenthesis String 验证括号字符串

2021年09月15日 阅读数：4

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:html

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

Example 1:java

```Input: "()"
Output: True```

Example 2:python

```Input: "(*)"
Output: True```

Example 3:post

```Input: "(*))"
Output: True```

Note:this

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

Java:递归

```public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
} else if (s.charAt(i) == ')') {
if (low > 0) {
low--;
}
high--;
} else {
if (low > 0) {
low--;
}
high++;
}
if (high < 0) {
return false;
}
}
return low == 0;
}
```

Python:

```class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
lower, upper = 0, 0  # keep lower bound and upper bound of '(' counts
for c in s:
lower += 1 if c == '(' else -1
upper -= 1 if c == ')' else -1
if upper < 0: break
lower = max(lower, 0)
return lower == 0  # range of '(' count is valid　　```

Python:

```def checkValidString(self, s):
cmin = cmax = 0
for i in s:
if i == '(':
cmax += 1
cmin += 1
if i == ')':
cmax -= 1
cmin = max(cmin - 1, 0)
if i == '*':
cmax += 1
cmin = max(cmin - 1, 0)
if cmax < 0:
return False
return cmin == 0
```

Python:

```def checkValidString(self, s):
cmin = cmax = 0
for i in s:
cmax = cmax-1 if i==')' else cmax+1
cmin = cmin+1 if i=='(' else max(cmin - 1, 0)
if cmax < 0: return False
return cmin == 0　```

Python: TLE

```class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
return self.helper(s, 0)

def helper(self, s, count):
# if not s:
#     return count == 0
if count < 0:
return False

for i in xrange(len(s)):
if s[i] == '(':
count += 1
elif s[i] == ')':
if count <= 0:
return False
else:
count -= 1
else:
return self.helper(s[i+1:], count+1)  or \
self.helper(s[i+1:], count)  or \
self.helper(s[i+1:], count-1)

return count == 0

if __name__ == '__main__':
print Solution().checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())")　　```

C++:

```class Solution {
public:
bool checkValidString(string s) {
stack<int> left, star;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '*') star.push(i);
else if (s[i] == '(') left.push(i);
else {
if (left.empty() && star.empty()) return false;
if (!left.empty()) left.pop();
else star.pop();
}
}
while (!left.empty() && !star.empty()) {
if (left.top() > star.top()) return false;
left.pop(); star.pop();
}
return left.empty();
}
};
```

C++:

```class Solution {
public:
bool checkValidString(string s) {
return helper(s, 0, 0);
}
bool helper(string s, int start, int cnt) {
if (cnt < 0) return false;
for (int i = start; i < s.size(); ++i) {
if (s[i] == '(') {
++cnt;
} else if (s[i] == ')') {
if (cnt <= 0) return false;
--cnt;
} else {
return helper(s, i + 1, cnt) || helper(s, i + 1, cnt + 1) || helper(s, i + 1, cnt - 1);
}
}
return cnt == 0;
}
};
```

C++:

```class Solution {
public:
bool checkValidString(string s) {
int low = 0, high = 0;
for (char c : s) {
if (c == '(') {
++low; ++high;
} else if (c == ')') {
if (low > 0) --low;
--high;
} else {
if (low > 0) --low;
++high;
}
if (high < 0) return false;
}
return low == 0;
}
};
```

[LeetCode] 20. Valid Parentheses 合法括号