Tasks Details
easy
1.
Brackets
Determine whether a given string of parentheses (multiple types) is properly nested.
Task Score
0%
Correctness
0%
Performance
0%
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}" where U is a properly nested string;
- S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
function solution($S);
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
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 ')'.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used PHP
Total time used 57 minutes
Effective time used 57 minutes
Notes
not defined yet
Task timeline
Code: 02:43:01 UTC,
java,
autosave
Code: 02:46:25 UTC,
php,
verify,
result: Failed
Analysis
Code: 03:39:30 UTC,
php,
verify,
result: Failed
function solution($S) {
$ans = 0;
// rb: round bracket, sb: square bracket, br: brace
$rb = $sb = $br = 0;
// Split by one
$A = str_split($S, 1);
$N = count($A);
if(0 != ($N % 2)) {
return $ans;
}
while(($c = array_shift($A)) == true) {
if($c = '(' && $rb == 0) { $rb++; }
if($c = '[' && $sb == 0) { $sb++; }
if($c = '{' && $br == 0) { $br++; }
if($c = '}') { $br--; }
if($c = ']') { $sb--; }
if($c = ')') { $rb--; }
}
if(($rb || $sb || $br) == 0) {
$ans = 1;
} else {
$ans = 0;
}
return $ans;
}
Analysis
Code: 03:39:37 UTC,
php,
verify,
result: Failed
function solution($S) {
$ans = 0;
// rb: round bracket, sb: square bracket, br: brace
$rb = $sb = $br = 0;
// Split by one
$A = str_split($S, 1);
$N = count($A);
if(0 != ($N % 2)) {
return $ans;
}
while(($c = array_shift($A)) == true) {
if($c = '(' && $rb == 0) { $rb++; }
if($c = '[' && $sb == 0) { $sb++; }
if($c = '{' && $br == 0) { $br++; }
if($c = '}') { $br--; }
if($c = ']') { $sb--; }
if($c = ')') { $rb--; }
}
if(($rb || $sb || $br) == 0) {
$ans = 1;
} else {
$ans = 0;
}
return $ans;
}
Analysis
Code: 03:39:40 UTC,
php,
final,
score:
0
function solution($S) {
$ans = 0;
// rb: round bracket, sb: square bracket, br: brace
$rb = $sb = $br = 0;
// Split by one
$A = str_split($S, 1);
$N = count($A);
if(0 != ($N % 2)) {
return $ans;
}
while(($c = array_shift($A)) == true) {
if($c = '(' && $rb == 0) { $rb++; }
if($c = '[' && $sb == 0) { $sb++; }
if($c = '{' && $br == 0) { $br++; }
if($c = '}') { $br--; }
if($c = ']') { $sb--; }
if($c = ')') { $rb--; }
}
if(($rb || $sb || $br) == 0) {
$ans = 1;
} else {
$ans = 0;
}
return $ans;
}
Analysis summary
The following issues have been detected: wrong answers, timeout errors.
For example, for the input '([)()]' the solution returned a wrong answer (got 1 expected 0).
Analysis
expand all
Correctness tests
1.
0.004 s
WRONG ANSWER,
got 1 expected 0
2.
0.004 s
WRONG ANSWER,
got 1 expected 0
3.
0.004 s
WRONG ANSWER,
got 1 expected 0
4.
0.004 s
WRONG ANSWER,
got 1 expected 0
5.
0.004 s
WRONG ANSWER,
got 1 expected 0
1.
0.004 s
WRONG ANSWER,
got 0 expected 1
simple_grouped
simple grouped positive and negative test, length=22
simple grouped positive and negative test, length=22
✘
WRONG ANSWER
got 1 expected 0
got 1 expected 0
1.
0.004 s
OK
2.
0.004 s
WRONG ANSWER,
got 1 expected 0
3.
0.004 s
WRONG ANSWER,
got 1 expected 0
4.
0.004 s
WRONG ANSWER,
got 1 expected 0
5.
0.004 s
OK
expand all
Performance tests
large1
simple large positive test, 100K ('s followed by 100K )'s + )(
simple large positive test, 100K ('s followed by 100K )'s + )(
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.14 sec.
running time: >6.00 sec., time limit: 0.14 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.14 sec.
2.
0.004 s
WRONG ANSWER,
got 1 expected 0
3.
0.288 s
TIMEOUT ERROR,
running time: 0.29 sec., time limit: 0.10 sec.
large2
simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()
simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()
✘
WRONG ANSWER
got 1 expected 0
got 1 expected 0
1.
0.004 s
OK
2.
0.004 s
WRONG ANSWER,
got 1 expected 0
3.
0.004 s
OK
large_full_ternary_tree
tree of the form T=(TTT) and depth 11, length=177K+
tree of the form T=(TTT) and depth 11, length=177K+
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.13 sec.
running time: >6.00 sec., time limit: 0.13 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.13 sec.
multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
✘
TIMEOUT ERROR
running time: 3.50 sec., time limit: 0.10 sec.
running time: 3.50 sec., time limit: 0.10 sec.
1.
3.504 s
TIMEOUT ERROR,
running time: 3.50 sec., time limit: 0.10 sec.
2.
0.008 s
OK
3.
3.504 s
TIMEOUT ERROR,
running time: 3.50 sec., time limit: 0.10 sec.
4.
3.548 s
TIMEOUT ERROR,
running time: 3.55 sec., time limit: 0.10 sec.
5.
3.516 s
TIMEOUT ERROR,
running time: 3.52 sec., time limit: 0.10 sec.
broad_tree_with_deep_paths
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
✘
TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.11 sec.
running time: >6.00 sec., time limit: 0.11 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.11 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.11 sec.