Valid Parenthesis String
Created: April 16, 2020 by [lek-tin]
Last updated: April 16, 2020
Given a string containing only three types of characters:
'*', 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.
Input: "()" Output: True
Input: "(*)" Output: True
Input: "(*))" Output: True
- The string size will be in the range [1, 100].
class Solution: def checkValidString(self, s: str) -> bool: opens, closes = 0, 0 for c in s: opens += 1 if c == "(" else -1 closes -= 1 if c == ")" else -1 if closes < 0: break opens = max(opens, 0) return opens == 0