Interview challenge · easy · stack, string
Valid Parentheses
El reto
El enunciado va en inglés, igual que en el vídeo.
Given a string s containing only the characters ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type of bracket, and brackets must close in the correct order.
Example
"()" -> true
"([]{})" -> true
"(]" -> false
"([)]" -> falseIdea: a stack. Push every opening bracket; on a closing one, the top of the stack must be its partner. At the end the stack must be empty. Time O(n), space O(n).
La solución
# Valid Parentheses - ayotl.dev
def is_valid(s):
# each closer -> the opener it needs
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
# the last opener must match
if not stack:
return False
if stack.pop() != pairs[ch]:
return False
else:
stack.append(ch) # remember it
# valid only if nothing is left open
return not stack
for s in ["()", "([]{})", "(]", "([)]"]:
print(s, is_valid(s))
$ python3 valid_parentheses.py
() True
([]{}) True
(] False
([)] False