Valid Parantheses

https://neetcode.io/problems/validate-parentheses?list=neetcode150

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

C1. Every open bracket is closed by the same type of close bracket. C2. Open brackets are closed in the correct order. C3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Solution

class Solution:
	CLOSING_TO_OPENING = {
		")": "(",
		"}": "{",
		"]": "["
	}
	
	def isValid(self, s: str) -> bool:
		# INVARIANT: `s` consists of ( ) { } [ and ].
		if len(s) == 0:  # CASE: Empty string
			return False
			
		stack: list[str] = []
		for ch in s:
			if ch in self.CLOSING_TO_OPENING:  # CASE: `ch` is closing
				opening = self.CLOSING_TO_OPENING[closing := ch]
				if len(stack) != 0 and stack[-1] != opening:  # CASE: C2, C3
					return False
				stack.pop()
			else:  # CASE: `ch` is opening
				stack.append(ch)
				
		return len(stack) != 0  # CASE: C1