CHECK THAT EVERY BRACKET CLOSES IN THE RIGHT ORDER. PUSH EACH OPENING BRACKET ONTO A STACK; EACH CLOSING BRACKET MUST MATCH THE OPENER ON TOP. THE STRING IS VALID ONLY WHEN THE STACK ENDS EMPTY.
BRACKETS MUST CLOSE IN THE REVERSE ORDER THEY OPENED. A STACK REMEMBERS THE OPENERS: PUSH EACH ONE, AND WHEN A CLOSER ARRIVES IT HAS TO MATCH THE OPENER ON TOP. IF IT DOES, POP IT. IF IT DOES NOT, OR THE STACK IS EMPTY, THE STRING IS INVALID.
THE BLUE TILE IS THE CHARACTER BEING SCANNED. TAN TILES ON THE STACK ROW ARE OPENERS WAITING TO CLOSE, NEWEST ON THE RIGHT. WHEN A CLOSER MATCHES THE TOP, A GREEN ARC LINKS THE PAIR AND THE OPENER LEAVES THE STACK. ONCE THE STACK IS EMPTY AGAIN, EVERY TILE TURNS GOLD.
1def is_valid(s):2 stack = []3 brackets = {4 "}": "{",5 "]": "[",6 ")": "("7 }89 for c in s:10 if c in brackets:11 if stack and stack[-1] == brackets[c]:12 stack.pop()13 else:14 return False15 else:16 stack.append(c)1718 return not stack
ONE PASS OVER THE STRING. EACH CHARACTER IS PUSHED OR POPPED AT MOST ONCE.
THE STACK CAN HOLD EVERY OPENER IF NONE OF THEM CLOSE, SO UP TO N IN THE WORST CASE.