https://leetcode.com/problems/valid-parentheses/
Valid Parentheses
Total Accepted: 72044 Total Submissions: 267703 Difficulty: Easy
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
My code:
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stk = []
def peek():
return stk[-1] if len(stk) > 0 else None
for k in s:
if k == ")":
if peek() == "(":
stk.pop()
else:
return False
elif k == "]":
if peek() == "[":
stk.pop()
else:
return False
elif k == "}":
if peek() == "{":
stk.pop()
else:
return False
else:
stk.append(k)
return stk == []
More elegant (Ref: https://leetcode.com/discuss/19900/simple-python-solution-with-stack):
class Solution:
# @return a boolean
def isValid(self, s):
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
# Other invalid characters
return False
return stack == []
Idea:
Stack will be empty if the string is valid. When you meet “)”, “]” or “}”, you check if the first element in stack is “(“, “[” or “{” correspondingly.