LC678 - Valid Parenthesis String

Problem

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

Solution

Greedy

Seems to be a parsing problem, solvable in $O(n)$ with no extra space used.

def checkValidString(self, s: str) -> bool:
	leftMin = 0
	leftMax = 0

	
	for char in s:
		if char == '(':
			leftMin += 1
			leftMax += 1
		elif char == ')':
			leftMin -= 1
			leftMax -= 1
		# char is **
		else: 
			leftMin -= 1
			leftMax += 1

		# Reset to 0 because wilds can be left unused
		if leftMin < 0:
			leftMin = 0

		# more rights than left + wild
		if leftMax < 0:
			return False

	# True unless left > right
	if leftMin == 0:
		return True
		
	return False