Valid Parentheses
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
A string contains only ( ) { } [ ]. Check that every bracket is closed by the correct type, in the correct order.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which opening bracket must a closing bracket match?
- Hint 2The most recent one that is still open. What structure gives you the most recent item?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Nested boxes: you open a big box, inside it a medium box, inside that a small box. To tidy up you must close the small box first, then the medium, then the big one. Keep a pile of the boxes you have opened (a stack of plates). When a closing lid comes, it must match the box on top of the pile; if the pile is empty or the top box is of another kind, something is wrong.
- The obvious way
Repeatedly delete matching "()", "[]", "{}" pairs from the string until nothing changes: O(n²).
- The key insight
Walk through the string with a pile. An opening bracket goes on the pile. A closing bracket must find its matching opening bracket on top of the pile; take it off. If it does not match, or the pile is empty, answer False. At the end the pile must be empty.
- The algorithm
- Start with an empty pile.
- Opening bracket? Put it on the pile.
- Closing bracket? The top of the pile must be its matching opener: if yes remove it, otherwise answer False.
- At the end, an empty pile means True.
Watch it run
Exampletext = "({[]})"
( is opening: put it on the pile.
pile: (
Where people slip
- Check for an empty pile before taking from it, e.g. for the text ")".
- Return pile-is-empty at the end: "(((" has no mismatch but is still invalid.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_valid(text):
pairs = {")": "(", "]": "[", "}": "{"} # closer -> its opener
pile = []
for bracket in text:
if bracket in pairs: # a closing bracket
if not pile or pile.pop() != pairs[bracket]:
return False
else:
pile.append(bracket) # an opening bracket
return not pileNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.