Medium

Valid Parenthesis String

LAB

Return true if * can be treated as (, ), or empty to make s a valid parentheses string.

EXAMPLES

Example 1

Input
{
  "s": "(*)"
}

Output
true

FUNCTION SHAPE

s: string→bool

SOLUTION NOTE

Greedy two-pass: first pass treats '*' as '(', second pass treats '*' as ')'. Both must succeed.

Reveal reference solution +

pythonREFERENCE

def checkValidString(self, s: str) -> bool:
    def check(s, open_char):
        balance = 0
        for c in s:
            balance += 1 if c == open_char or c == '*' else -1
            if balance < 0:
                return False
        return True

    return check(s, '(') and check(s[::-1], ')')

TimeO(n)

SpaceO(1)

Open on LeetCode ↗