Valid Parentheses

Problem

Lets look at the question at hand

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

An input string is valid if:

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

Click on the above card to go to the problem on leetcode.

Approach

Basically, we need to check if the first parenthesis is the same as the last parenthesis.

We’re going to use a stack, since elements in a stack are FILO (First In Last Out) or LIFO (Last In First Out), which is pretty much how we want the parenthesis to be too.

Initialize an empty stack

Append to the stack

Iterate over the input string and filter out the required parentheses.
Only if the parenthesis is an opening parenthesis, append it to the stack.

Closing parentheses

When you encounter a closing parenthesis, ensure you are checking if the stack is empty or not first.
And also check if the closing bracket matches with its corresponding opening bracket by checking the last element of the stack which is stk[-1].
If the closing bracket does not match the last appended element into the stack, return False.

If control does not flow into this condition then just pop the last element - stk.pop()

True

Finally, all of the elements would be popped out if the parentheses are valid.
Now all you you need to check is, whether the stack is empty or not. If its empty, return True.

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack = [] 
        for c in s: 
            if c in '([{': 
                stack.append(c) 
            else: 
                if not stack or \
                    (c == ')' and stack[-1] != '(') or \
                    (c == '}' and stack[-1] != '{') or \
                    (c == ']' and stack[-1] != '['):
                    return False 
                stack.pop() 
        return not stack

This is an easy problem but tests your basics with stack. There are other solutions too, but this one’s pretty simple compared to the more complex ones out there.