blob: be5ad6c675548ce36b7f777887de32dd1d557034 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
# 678. Valid Parenthesis String
"""
given a string 's' containing only three types of characters, return true if
's' is valid. the following rules define a valid string: 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. start could be treated as a single right
parenthesis, a single left parenthesis, or an empty string.
"""
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
cmin, cmax = 0, 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
if __name__ == "__main__":
obj = Solution()
print(obj.checkValidString("()"))
print(obj.checkValidString("(*)"))
print(obj.checkValidString("(*))"))
|