Valid Parentheses
A string of brackets is balanced when every opening bracket is closed by a bracket of the same kind, and the pairs sit inside each other instead of overlapping. There are three kinds: round (), square [] and curly {}.
For example, {[()()]} is balanced: each pair closes inside the pair that wraps it. But {(}) is not: the curly bracket closes while the round bracket opened after it is still waiting. A string like (( is not balanced either, because nothing closes the two openers.
Write a function named isValid that gets a string s made only of the characters (, ), [, ], { and }, and returns true when its brackets are balanced and false otherwise.
Balanced means every closing bracket matches the most recent opening bracket that is still open, the two are the same kind, and no opening bracket is left open at the end.
Constraints: 1 ≤ s.length ≤ 10^4.
Function
- arg1string
- Returnsboolean
Examples
- Input
- arg1 = "[]{}()"
- Output
- true
- Input
- arg1 = "{[()()]}"
- Output
- true
- Input
- arg1 = "{(})"
- Output
- false
+13 hidden tests on Submit
Hints
Open them one at a time. Each one gives away a little more.
Read the string from left to right. When a closing bracket arrives, which opening bracket is it allowed to close?
It can only close the opening bracket that was opened most recently and is still open. Last opened, first closed: that is exactly the order a stack keeps.
Push every opening bracket onto a stack. On a closing bracket, the stack must not be empty and its top must be the same kind; pop it and continue. When the string ends, it is balanced only if the stack is empty.
A full walkthrough of this problem is on its way.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def isValid(s):
# Write code hereCase 1
Case 2
Case 3
Input
arg1 = "[]{}()"Expected
true