leetcode 20. Valid Parentheses

 

Example 4 : s = "{()}" output = true;

 

예시를 보면 소/중/대괄호가 짝지어서 나오고 Example 4 와 같이 속에있을수도있다.

 

처음에는 String 의 Char.At(i) 가 ( 혹은 { 혹은 [ 일때 Char.At(i +1) 이 ) 혹은 } 혹은 ] 인것을 확인했는데

example 4 때문에 그건 불가능했다.

 

해당문제는 여는 괄호가 나오면 그다음엔 무조건 닫는 괄호가 나와야하기때문에 여는 괄호가 나오면 stack 에 저장해두고, 더이상 여는 괄호가 없으면 stack 에서 가장 나중에 저장된 괄호를 지우는 방식으로 진행했다.

 

class Solution {
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
    }
}

 

여는괄호인지를 알기위해서 map을 만들어줬다.

class Solution {
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        
        for (int i=0; i<s.length(); i++) {
        	char c = s.charAt(i);
            
            if (map.containsKey(c)) { //여는 괄호가 나왔다면
            	stack.push(c);
            } else {
            	if (c != map.get(stack.pop()) {
                   return false;
                }
            }
        }
        
        return stack.length == 0;
    }
}

 

 여는 괄호가 나왔다면 stack에 넣어주고 

닫는괄호가 나왔다면, stack에 있는 여는괄호를 불러서 map.get 으로 나온 value와 비교하였다.

 

그리고 모든 닫는괄호가 정상적으로 짝지어나왔다면 stack.length 는 0일 것이므로 return 해줬다.

 

그런데 이렇게 하면 s="]" 일때 .. stack 에도 값이 없기때문에 else 로 빠지지만, 갈곳이없다..!

 

때문에 empty 도 같이 봐준다.

 

class Solution {
    public boolean isValid(String s) {
    	Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
        
        for (int i=0; i<s.length(); i++) {
        	char c = s.charAt(i);
            
            if (map.containsKey(c)) { //여는 괄호가 나왔다면
            	stack.push(c);
            } else {
            	if (stack.isEmpty() || c != map.get(stack.pop())) {
                   return false;
                }
            }
        }
        
        return stack.size() == 0;
    }
}