readme.md

678. Valid Parenthesis String

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

The following rules define a valid string:

• 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 "".

Example 1:

Input: s = "()" Output: true

Example 2:

Input: s = "(*)" Output: true

Example 3:

Input: s = "(*))" Output: true

Constraints:

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'.

Solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        # First pass: left to right
        leftBalance = 0
        for char in s:
            if char == '(' or char == '*':
                leftBalance += 1
            else:
                leftBalance -= 1
            # If the balance goes negative, we have more ')' than '(' and '*'
            if leftBalance < 0:
                return False

        # Second pass: right to left
        rightBalance = 0
        for char in reversed(s):
            if char == ')' or char == '*':
                rightBalance += 1
            else:
                rightBalance -= 1
            # If the balance goes negative, we have more '(' than ')' and '*'
            if rightBalance < 0:
                return False

        return True

Thoughts

This solution is a lot more easier to understand than neetcode's solution.

Time Complexity

O(n), where n is the length of the string s. We make two passes through the string.

Space Complexity

O(1). We use only a few variables for the counters, which use constant space.