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

Links

Question here and solution here

Solution

concept

we keep track of the number of minimum and maximum possible left parentheses depends on the condition The left_min and left_max represents the valid possible left parentheses we can have. If at any point left_max < 0 we should return False because we will never recover from that. We should return True if at the end left_min == 0 since it is possible to cancel out all left parenthesses.

Whenever left_min drop below 0 we should reset it to 0 since we are after valid parenthesis (we cannot choose * in a way that makes left parenthesis negative i.e. make * a ) to make it invalid) We do not need to worry about ) making it negative without being detected as ) will decrement both left_min and left_max and that will trigger the left_max < 0 condition and make it False.

code

class Solution:
    """
    greedy solution
    time complexity: O(n)
    space complexity: O(1)

    we keep track of the number of minimum and maximum possible left parentheses
    """
    def checkValidString(self, s: str) -> bool:
        left_max, left_min = 0, 0

        for char in s:
            if char == "(":
                left_max += 1
                left_min += 1
            elif char == ")":
                left_max -= 1
                left_min -= 1
            else:
                left_min -= 1
                left_max += 1
            # if left_max < 0, then it is impossible to balance the string since we do not have enough left parentheses
            # only ) will decrease left_max -> ))( will not be balanced
            if left_max < 0:  
                return False
            # reset left_min to 0 because we need valid string
            if left_min < 0:
                left_min = 0
        
        return True if left_min == 0 else False
        
class Solution:
    """
    DP with memoization
    time complexity: O(n^3)
    space complexity: O(n^2)
    """
    def checkValidString(self, s: str) -> bool:
        dp = {(len(s), 0): True}  # key=(i, leftCount) -> isValid

        def dfs(i, left):
            if i == len(s) or left < 0:
                return left == 0
            if (i, left) in dp:
                return dp[(i, left)]

            if s[i] == "(":
                dp[(i, left)] = dfs(i + 1, left + 1)
            elif s[i] == ")":
                dp[(i, left)] = dfs(i + 1, left - 1)
            else:
                dp[(i, left)] = (
                    dfs(i + 1, left + 1) or dfs(i + 1, left - 1) or dfs(i + 1, left)
                )
            return dp[(i, left)]

        return dfs(0, 0)

Complexity

time: $O(n)$
space: $O(1)$