20. Valid Paranthesis

Problem Statement in English

You’re given a string s containing just the characters '(', ')', '{', '}', '[' and ']'. Determine if the input string is valid.

Approach

We can use a stack to keep track of the opening brackets.

When we encounter an opening bracket, we push it onto the stack.

When we encounter a closing bracket, we check if it matches the top of the stack. If it does, we pop the stack; if it doesn’t, the string is invalid. At the end, if the stack is empty, the string is valid.

And we’re done!

Solution in Python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        d = {")":"(", "]":"[", "}":"{"}

        for char in s:
            if char not in d:
                stack.append(char)
            elif stack and stack[-1] == d[char]:
                stack.pop()
            else:
                return False

        return not stack

Complexity

• Time: $O(n)$
  Since we traverse the input string once, where n is the length of the string.

• Space: $O(n)$
  Since we might need to store all characters in the stack in the worst case.

And we are done.