October 4Medium

Valid parenthesis string

String
Dynamic Programming
Stack
Greedy
Bracket Sequences

Problem

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string: 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 "".

Solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        wildcard = []
        opened = []
        for i in range(len(s)):
            if s[i] == "(":
                opened.append(i)
            elif s[i] == "*":
                wildcard.append(i)
            else:
                if opened:
                    opened.pop()
                elif wildcard:
                    wildcard.pop()
                else:
                    return False

        while opened:
            if not wildcard or wildcard.pop() < opened.pop():
                return False

        return True