678_Valid Parenthesis String

678. Valid Parenthesis String

Level: medium

Tag: string

Question

Given a string containing only three types of characters: '(', ')' and '*', 
write a function to check whether this string is valid. 

We define the validity of a string by these rules:
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.
5. An empty string is also valid.

Example1

Input: "()"
Output: True

Example2

Input: "(*)"
Output: True

Example3

Input: "(*))"
Output: True

Idea

"*" represent either ( or ). It won't represent both. (Because otherwise they can balance out.)

So there are two major cases that make the string not valid:

• If * represent ( , scan from left to right. If the number of ) is larger than the total number of * and ( at any point, then this string is invalid.

• If * represent ), scan from right to left. If the number of ( is larger than the total number of * and ) at any point, then this string is invalid.

Complexity

• Time:$O(n)$

• Space:$O(1)$

Solution

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """

        leftcnt, rightcnt = 0, 0

        # scan from left to right
        # * represent (
        for i in s:
            if i == ")":
                leftcnt -= 1
            else:
                leftcnt += 1
            if leftcnt < 0:
                return False

        # scan from right to left
        # * represent )
        for j in s[::-1]:
            if j == "(":
                rightcnt -= 1
            else:
                rightcnt +=1
            if rightcnt < 0:
                return False

        return True