Valid Parentheses (Leet Code-20)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 20. This is a Leet code problem named Valid Parentheses. We will solve it using python and it is the best space and time-optimized solution.

Question of Valid Parentheses

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.

Example

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Constraints

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Approach to solve Valid Parentheses

To solve this we traverse through each character of string which consists of sign {}()[] only. When an open parenthesis comes like {, [, ( we push it into the stack. And when the closing parenthesis comes like }, ], ) we compare it from the top of the stack. If the closing parenthesis matches with the top of stack then we pop the stack otherwise we return the false.

Algorithm

This method performs the following steps for a given input array:

Create a stack to store Parentheses.
Repeat steps from 3 to 10 till there is a parenthesis in the string.
Check if it opening Parentheses then push it into stack.
If it is closing Parentheses then check the length of the stack is greater than 0 or not.
If Yes then do steps 6 and 7 otherwise do step 9.
pop the last element.
if the element is not the opposite of popped element then return false.
end if
return false
end if
end for
return true

Python Code for Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        #stack to store Parentheses
        stack = []
        
        #run through each Parentheses
        for i in s:
            #Check if it opening Parentheses then push it into stack
            if i=='(' or i =='[' or i=='{':
                stack.append(i)
            #If it closing Parentheses then check length of stack is greater than 0 or not
            elif(len(stack)):                
                #pop the last element
                el = stack.pop()
                #if element is not opposite of popped element than return false
                if el=='(' and i !=')':
                    return False
                elif el=='[' and i !=']':
                    return False
                elif el=='{' and i !='}':
                    return False
            #If above 2 condition fails return false
            else:
                return False
        #if there is any Parentheses in stack return false
        if(len(stack)):
            return False
        #otherwise return true
        else:
            return True