[Codility] Brackets

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 consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

 

  Nested 되려면 (, {, [ 등이 나왔을때 그 역순대로 ], }, ) 가 Pair로 나와야한다. 따라서 Stack을 이용해 구현해보았다. 유의할점은 Stack에 원소가 없을때 ], }, ) 등이 나오면 Pop 할 원소가 없기 때문에 0을 리턴해주는 것만 유의해주면된다. 또한, 반대로 남은 (, {, [ 가 있을 때는 Stack의 Size가 0보다 크기 때문에 그 경우에도 0을 리턴해줘야한다.

import java.util.*;

class Solution {
    public int solution(String S) {
        
        Stack<Character> bracket = new Stack<>();
        
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == '(' || S.charAt(i) == '{' || S.charAt(i) == '['){
                bracket.push(S.charAt(i));
            }
            else{
                if(bracket.empty()){
                    return 0;
                }
                
                if(S.charAt(i) == ')' && bracket.peek() == '('){
                    bracket.pop();
                }
                else if(S.charAt(i) == '}' && bracket.peek() == '{'){
                    bracket.pop();
                }
                else if(S.charAt(i) == ']' && bracket.peek() == '['){
                    bracket.pop();
                }
                else{
                    return 0;
                }
            }
        }
        
        if(!bracket.empty()){
            return 0;
        }
        
        return 1;
    }
}