Tags: "leetcode", "greedy", access_time 1-min read

Valid Parenthesis String

Created: April 16, 2020 by [lek-tin]

Last updated: April 16, 2020

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:

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

Input: "()"
Output: True

Example 2

Input: "(*)"
Output: True

Example 3

Input: "(*))"
Output: True

Note

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

Solution

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