678.Valid_Parenthesis_String(Medium).md

678. Valid Parenthesis String (Medium)

Date and Time: Aug 18, 2024, 23:23 (EST)

Link: https://leetcode.com/problems/valid-parenthesis-string/

Question:

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 '*'.

Walk-through:

1. We use leftMin, leftMax to keep track of the minimum number and maximum number of opening parenthesis ( we could have. If leftMax < 0 that means the max number of ( we can have is never enough, which doesn't make sense, because leftMax should either be 0 (s = "*") or leftMax > 0 when not more ) than (.

2. We check if i == '(', we increment both leftMin and leftMax. If i == ')', we decrement both leftMin, leftMax. If i == '*', we want leftMin -= 1 and leftMax += 1, because we assume leftMin takes ) and leftMax takes * as (.

3. Finally, we return leftMin == 0, because the minimum of ( we can have should be 0, if we have leftMin > 0 that means ( have no enough ), which is not a valid string.

When leftMin < 0, we reinitialize leftMin = 0, think about s = "(((***", leftMax = 6 and leftMin = 0 which should return true because we can change every asterisk symbol for a right parenthesis symbol. But string s = "(((****" our leftMin will become -1. But in this case it doesn't make any sense for us to turn every asterisk into a right parenthesis because it will make the whole string invalid, that's why we treat one asterisk as an empty string and reset our leftMin to 0. And we don't afraid of a case like this s = "())" where we also should reset our leftMin because our leftMax will become less than 0 and it will return false.

Python Solution:

class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin = leftMax = 0
        for i in s:
            if i == '(':
                leftMin, leftMax = leftMin + 1, leftMax + 1
            elif i == ')':
                leftMin, leftMax = leftMin - 1, leftMax - 1
            else:
                leftMin, leftMax = leftMin - 1, leftMax + 1
            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin = 0
        return leftMin == 0

Time Complexity: $O(n)$
Space Complexity: $O(1)$