Valid Parentheses

20. Valid Parentheses

Difficulty: Easy

Related Topics: String, Stack

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.

Example 1:

Input: s = “()” Output: true

Example 2:

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

Example 3:

Input: s = “(]” Output: false

Code:

class Solution:
    def isValid(self, s: str) -> bool:
        pardict = { ')':'(', ']':'[', '}':'{'}
        stack = []
        for i in s:
            if i not in pardict:
                stack.append(i)
            else:
                if len(stack) == 0:
                    return False
                elif stack[-1] != pardict[i]:
                    return False
                else:
                    stack.pop()
        if stack:
            return False
        else:
            return True

Feedbacks:

I first create a dictionary storing closing brackets as keys and opening brackets as values and a stack to store opening brackets from string s. As I traverse through the string, if it is an opening bracket, I append it to stack. If it is not an opening bracket, I check is last element appended to stack is corresponding bracket and then remove it. Else, I can return False because it means opening bracket and closing bracket don’t match.