Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Valid Parentheses

LeetCode #20Easy
The top is the bracket that must close next

Given a string of brackets containing the characters (), [], and {}, determine whether it is valid: every opening bracket must be closed by a matching bracket of the same type, and brackets must close in the correct order.

Asked atAmazonMetaGoogleMicrosoft
step 1 / 21
(
[
{
}
]
)
[0][1][2][3][4][5]
Brute force · delete adjacent pairs
▸
1given s
2repeat:
3    find an adjacent pair "()", "[]" or "{}"
4    if found: delete it
5    else: break
6return s is empty
state
  • s"([{}])"

line 1Is every bracket closed by the right partner, in the right order? First idea: an adjacent pair like "()" or "{}" is definitely valid — delete it and ask the same question about what remains.