The string contains only brackets. Round, square and curly. Check that every opening bracket is closed by the same type, in the right order.
DSA Animator › DSA Revision › Stack › Valid Parentheses
Remember: last opened, first closed, so use a stack. Push the expected closing bracket to make matching trivial. The video solves Valid Parentheses (LeetCode 20, Easy) with the Stack pattern from the Stack topic, and you can replay every step in the interactive Valid Parentheses animation.
The string contains only brackets. Round, square and curly. Check that every opening bracket is closed by the same type, in the right order.
Round open, square open and close, curly open and close, then round close: that is valid. But round open, square open, then round close is invalid, because the square bracket must close first.
Just counting opening and closing brackets is not enough. In the second example the counts match, but the order is wrong.
The bracket opened last must be closed first. That is exactly how a stack works. When you see an opening bracket, push it. When you see a closing bracket, pop the top, and check that the pair matches. At the end, the stack must be empty.
Round open: push. Square open: push. Square close: the top is square open, a match, so pop. Curly open: push. Curly close: the top is curly open, a match, so pop. Round close: the top is round open, a match, so pop. The string ends and the stack is empty, so it is valid. In the second example, round close arrives while square open is on top, so there is no match, and the answer is false.
In code, use a stack. For an opening bracket, push its closing partner, which makes the comparison easy. For a closing bracket, return false if the stack is empty, or if the popped bracket is different. At the end, return true only if the stack is empty. It's O of n time and O of n space.
Remember: last opened, first closed, so use a stack. Push the expected closing bracket to make matching trivial.