Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
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 '()[]{}'
.Source
def valid_parentheses(s):
'''
Time Complexity O(n)
Space Complexity O(n)
'''
stack = []
for char in s:
if char in {'(', '[', '{'}: # make sure to use Hash table to store
stack.append(char) # this has a O(1) access
if char in {')', ']', '}'}:
if len(bstack) == 0 or (stack.pop() + char) not in {'()', '[]', '{}'}:
return False
return stack == []
def valid_parentheses(s):
'''
Time Complexity O(n)
Space Complexity O(n)
'''
stack = []
mapping = {'}': '{', ')': '(', ']': '['}
for char in s:
if char not in mapping:
stack.append(char)
else:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
return not stack
s = "()"
valid_parentheses(s)
True
s = "(]"
valid_parentheses(s)
False
s = "([)]"
valid_parentheses(s)
False
s = "{[]}"
valid_parentheses(s)
True
s = "()[]{}"
valid_parentheses(s)
True
s = "([)]"
valid_parentheses(s)
False
s = "{[]}"
valid_parentheses(s)
True
s = '('
valid_parentheses(s)
False
s = ')'
valid_parentheses(s)
False
s = ''
valid_parentheses(s)
True