678. Valid Parenthesis String

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: s = "()" Output: true

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

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

Solution Approach

The algorithm iterates through the string, tracking left and right parentheses counts. It handles ‘(‘ by incrementing both counts, ‘)’ by decrementing both if possible, and ‘*’ as flexible either as ‘(‘ or ‘)’. If there are more ‘)’ than ‘(‘, it returns False; otherwise, it returns True if all left parentheses are matched. Time complexity is O(n).

Algorithm

1. Initialize: Set counters l and r to 0.
2. Iterate: Go through each character p in the string. Increment l and r for ‘(‘. Decrement both if p is ‘)’ and l > 0; otherwise, decrement only r. For ‘*’, treat as ‘(‘ (increment l), ‘)’ (decrement r if l > 0), or an empty string. If r becomes negative, return False.
3. Check: Return True if l is 0, indicating all ‘(‘ are matched.

Implement

    class Solution:
    def checkValidString(self, s: str) -> bool:
        #               ( * )
        # l  at less r  1 1 0
        # r  no more r  1 2 1
        l = r = 0
        for p in s:
            if p == '(':
                l += 1
                r += 1
            elif p == ')':
                if l > 0: # notice to add checking here
                    l -= 1
                r -= 1
            else:
                if l > 0:
                    l -= 1
                r += 1
            if r < 0:
                return False
        return l == 0

    
    

Twitter  facebook  Email