Valid Parentheses: Stack*

First Thought: limping traversal, checking half the length of the string, incrementing traversing index by 2. --> problem: two types of cases possible: 옆에 연속으로 붙어 있는 괄호들, 아니면 괄호 안에 감싸는 괄호 조합

My Failed Solution:

class Solution {
    public boolean isValid(String s) {
        //traverse increment by two, check based on this index
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.putIfAbsent(c, 0);
            map.put(c, map.get(c)+1);
        }
        if (map.get('(')!=map.get(')')||map.get('{')!=map.get('}')||
           map.get('[')!=map.get(']')) return false;
        
        for (int i=0; i<s.length()/2; i++) {
            switch(s.charAt(i)) {
                case '(':
                    if (s.charAt(s.length()-i-1)!=')'&&s.charAt(i+1)!=')') {
                        return false;
                    }
                    break;
                case '{':
                    if (s.charAt(s.length()-i-1)!='}'&&s.charAt(i+1)!='}') {
                        return false;
                    }
                    break;
                case '[':
                    if (s.charAt(s.length()-i-1)!=']'&&s.charAt(i+1)!=']') {
                        return false;
                    }
                    break;
            }
        }
        
        return true;
    }
}

문제점: 케이스가 너무 많고 복잡해진다. 먼저 괄호 종류에 따라서 나누고, 그에 따라 연속성 케이스1 인지, 괄호안에 있는 케이스2 인지, 그 둘의 조합인지, 판단을 하고 그 방법을 flexible하게 다루기에는 너무 얽혀있다.

Ideal Solution: using Stack

Stack<Character> stack = new Stack<>();
for (int i=0; i<s.length(); i++) {
	 if (s.charAt(i)=='(') stack.push(')');
     else if (s.charAt(i)=='{') stack.push('}');
     else if (s.charAt(i)=='[') stack.push(']');
     else if (stack.isEmpty() || stack.pop()!=s.charAt(i)) return false;
}
return stack.isEmpty();

Catch Point

1. Intuition: 앞에 시작괄호가 있다면 무조건 뒤에 (어디인지는 모르겠지만) 닫는 괄호가 항상 나와야한다. First In Last Out의 structure랑 매우 관련이 깊다 -> stack을 사용할 수 있는지 생각해 볼 것.
2. 만약 닫는 괄호가 부족하거나 시작 괄호가 더 많다면 무조건 false이다 -> 예상하는 닫는 괄호가 아니거나, 아예 없는 경우 (스택이 빈 경우) false, 그리고 마지막에 남아있는 괄호가 있다면 (원래는 써여져야 했지만 안쓰여짐) 그럼 마지막에 false 처리를 해준다.
3. 결국에는, 시작 괄호를 안다면, 닫는 괄호가 무엇이 올 지 안다. 이를 예상값으로 push하고, 실제 만나는 괄호가 예상과는 다르다면, false를 리턴한다.