题目
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.
解题思路
代码
class Solution:
def checkValidString(self, s: str) -> bool:
l = r = 0
for c in s:
if c == '(':
l += 1
r += 1
elif c == ')':
if l > 0:
l -= 1
r -= 1
else:
if l > 0:
l -= 1
r += 1
if r < 0:
return False
return l == 0
