10969: Codility - Brackets
[Creator : ]
Description
Determine whether a given string of parentheses (multiple types) is properly nested.
A string $S$ consisting of $N$ characters is considered to be properly nested;if any of the following conditions is true:
A string $S$ consisting of $N$ characters is considered to be properly nested;if any of the following conditions is true:
- $S$ is empty;
-
$S$ has the form
"(U)"
or"\[U\]"
or"{U}"
whereU
is a properly nested string; -
$S$ has the form
"VW"
whereVandWare properly nested strings.
"{[()()]}"
is properly nested but "([)()]"
is not. Input
Write an efficient algorithm for the following assumptions:
- $N$ is an integer within the range $[0..200,000]$;
-
string $S$ is made only of the following characters:
'(', '{', '[', ']', '}'
and/or')'
.
Output
returns $1$ if $S$ is properly nested and $0$ otherwise.
Sample 1 Input
8
{[()()]}
Sample 1 Output
1
Sample 2 Input
6
([)()]
Sample 2 Output
0