Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()" Output: true

Example 2:

Input: s = "()[]{}" Output: true

Example 3:

Input: s = "(]" Output: false

Solution

We must start with an opening bracket, if we start with a closing bracket no matter what we do we cannot fix it.

We can add as many open brackets as we want, so long as they eventually close.

As soon as we find 2 matching brackets we can remove them from our stack.

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 1:
            return False
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for i in s:
            # add to stack to view it
            # if its a closing brace the top of our stack must have the opening brace
            if i in dict.values():
                # its an opening brace
                stack.append(i)
            elif i in dict.keys():
                # closing brace, we should have an opening brace
                # we cannot add a closing brace to the top of the stack
                if len(stack) == 0 or stack.pop() != dict[i]:
                    # if its not a valid brace return false
                    return False
            else:
                return False
        return stack == []
                

A Cleaner code would be:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {"]":"[", "}":"{", ")":"("}
        
        for c in s:
        	# if its a closing brace
        	if c in closeToOpen:
            	# We cannot have a closing brace and empty stack
                # as that would mean theres no opening braces
                # If the most recently added item to our stack is the opening brace of the thing we are tring to close
            	if stack and stack[-1] == closeToOpen[c]:
                	# remove the opening brace and do not append the closing brace as they are a pair
                	stack.pop()
                else:
                	# else either the stack is empty or we have a closing brace with no opening, returning false
                	return False
            else:
            	# else its an opening brace. We can add as many opening braces as we want so long as we eventually close them
            	stack.append(c)
        # if the stack is empty that means every opening brace has a closing brace
        # else if the stack is not empty, this was not true so we must fail
        return True if not stack else False