Tasks Details
easy
1.
Brackets
Determine whether a given string of parentheses (multiple types) is properly nested.
Task Score
100%
Correctness
100%
Performance
100%
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:
class Solution { public int solution(String 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 Java 8
Total time used 22 minutes
Effective time used 22 minutes
Notes
not defined yet
Task timeline
Code: 10:04:59 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return 1;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:5: error: ';' expected public static final int BALANCED = 1 ^ 1 error
Code: 10:05:15 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:36: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<>(){{ ^ Solution.java:52: error: cannot find symbol public List<T> stack; ^ symbol: class List location: class Stack<T> where T is a type-variable: T extends Object declared in class Stack Solution.java:9: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:11: error: cannot infer type arguments for Stack<> Stack<Character> stack = new Stack<>(); ^ reason: cannot infer type-variable(s) T (actual and formal argument lists differ in length) where T is a type-variable: T extends Object declared in class Stack Solution.java:36: error: cannot infer type arguments for HashMap<K,V> private Map<Character> language = new HashMap<>(){{ ^ reason: cannot use '<>' with anonymous inner classes where K,V are type-variables: K extends Object declared in class HashMap V extends Object declared in class HashMap Solution.java:55: error: cannot find symbol stack = new ArrayList<>(capacity); ^ symbol: class ArrayList location: class Stack<T> where T is a type-variable: T extends Object declared in class Stack 6 errors
Code: 10:05:46 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<>(){{ ^ Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:13: error: cannot infer type arguments for Stack<> Stack<Character> stack = new Stack<>(); ^ reason: cannot infer type-variable(s) T (actual and formal argument lists differ in length) where T is a type-variable: T extends Object declared in class Stack Solution.java:38: error: cannot infer type arguments for HashMap<K,V> private Map<Character> language = new HashMap<>(){{ ^ reason: cannot use '<>' with anonymous inner classes where K,V are type-variables: K extends Object declared in class HashMap V extends Object declared in class HashMap 4 errors
Code: 10:06:02 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<Character>(){{ ^ Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:13: error: cannot infer type arguments for Stack<> Stack<Character> stack = new Stack<>(); ^ reason: cannot infer type-variable(s) T (actual and formal argument lists differ in length) where T is a type-variable: T extends Object declared in class Stack Solution.java:38: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<Character>(){{ ^ 4 errors
Code: 10:06:41 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<Character>(){{ ^ Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:38: error: wrong number of type arguments; required 2 private Map<Character> language = new HashMap<Character>(){{ ^ 3 errors
Code: 10:07:04 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:38: error: cannot infer type arguments for HashMap<K,V> private Map<Character, Character> language = new HashMap<>(){{ ^ reason: cannot use '<>' with anonymous inner classes where K,V are type-variables: K extends Object declared in class HashMap V extends Object declared in class HashMap Solution.java:45: error: cannot find symbol return language.valueSet().contains(c); ^ symbol: method valueSet() location: variable language of type Map<Character,Character> 3 errors
Code: 10:07:23 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ Solution.java:38: error: cannot infer type arguments for HashMap<K,V> private Map<Character, Character> language = new HashMap<>(){{ ^ reason: cannot use '<>' with anonymous inner classes where K,V are type-variables: K extends Object declared in class HashMap V extends Object declared in class HashMap 2 errors
Code: 10:07:38 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int if (S.isEmpty() == 0 ) return BALANCED; ^ 1 error
Code: 10:07:55 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:22 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:51 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:59 UTC,
java,
final,
score: 
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
1.381 s
OK
2.
1.425 s
OK
3.
1.402 s
OK
4.
1.391 s
OK
5.
1.400 s
OK
1.
1.370 s
OK
1.
1.414 s
OK
2.
1.393 s
OK
3.
1.421 s
OK
4.
1.426 s
OK
5.
1.465 s
OK
expand all
Performance tests
1.
2.048 s
OK
2.
1.470 s
OK
3.
1.506 s
OK
1.
1.512 s
OK
2.
1.476 s
OK
3.
1.462 s
OK
1.
2.012 s
OK
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+
✔
OK
1.
1.648 s
OK
2.
1.644 s
OK
3.
1.637 s
OK
4.
1.659 s
OK
5.
1.533 s
OK
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+
✔
OK
1.
1.867 s
OK
2.
1.822 s
OK