20. Valid Parentheses
On This Page
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
First accepted
Idea:
- Loop through string
- If current “closes” the last in stack, then remove last from stack
- Else: add current to stack
class Solution:
def isValid(self, s: str) -> bool:
stack = []
par_dict = {'(': ')', '{': '}', '[': ']'}
last_value = None
for i in s:
second_value = par_dict.get(last_value, None)
if i == second_value:
stack.pop()
last_value = stack[-1] if stack else None
else:
stack.append(i)
last_value = i
return not stack
Better solution
class Solution:
def isValid(self, s: str) -> bool:
par_dict = {'(': ')', '{': '}', '[': ']'}
stack = []
for char in s:
if char in par_dict: # If it's an opening bracket, add it to the stack
stack.append(char)
elif stack: # If there's something in the stack
if char == par_dict[stack[-1]]:
# If it's a closing bracket for the last opened bracket, remove it from the stack.
stack.pop()
else: # It's not a closing bracket for the last opened bracket. Invalid string.
return False
else: # Not an opening bracket or closing bracket. Invalid string.
return False
return stack == []
