Valid Parentheses (Python)

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', … Read more Valid Parentheses (Python)

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.

Check it out: https://leetcode.com/problems/valid-parentheses/

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

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

Solution:


class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 != 0:
return False
dict = {'(' : ')', '[' : ']', '{' : '}'}
stack = []
for iin s:
if i in dict.keys():
stack.append(i)
else:
if stack == []:
return False
a = stack.pop()
if i!= dict[a]:
return False
return stack == []

Explanation:

Here we use stack validation and a dictionary! We need a Stack to store the last valid left part of the parentheses, the left parentheses are also taken as the key, and their values would be its right parentheses. So if we store the left parentheses inside the stack, and if we find a valid right part, pop it out of the stack. Think about the case ‘{[]}’, it is not hard to figure out, we need a Stack to store the last valid left part of parentheses, when next char is the valid right part, pop out the left part.

Another validation is to check if the length of the string is even, if it is odd, then it's obviously not a valid parenthesis (or) balanced parentheses! so a valid parentheses string’s length should always be even, we can add a check at the beginning. The worst-case scenario is when someone starts off the input as a ‘((((((((((‘ and so on.

GitHub

LinkedIn

Twitter

Instagram


Valid Parentheses (Python) was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

Source: Level Up Coding



Leave a Reply

Your email address will not be published. Required fields are marked *