This content originally appeared on Level Up Coding - Medium and was authored by Ritchie Pulikottil
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.
Check it out: https://leetcode.com/problems/valid-parentheses/
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: trueConstraints:
- 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.
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.
This content originally appeared on Level Up Coding - Medium and was authored by Ritchie Pulikottil
Ritchie Pulikottil | Sciencx (2021-09-03T14:11:52+00:00) Valid Parentheses (Python). Retrieved from https://www.scien.cx/2021/09/03/valid-parentheses-python/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.