[LeetCode] 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

이 문제는 괄호의 짝이 맞는 지 확인후 맞다면 True,틀리다면 False를 Return하는 문제이다. 나의 경우 착각했던 부분은

"( [ ) ]" 가 True라고 생각했다. 하지만 이는 False이다. 이 예시같은경우 )는 같은 타입의 ( 로 닫혀야하는데, [ 로 닫혀 이경우도 틀리게 본다는 것이다.(Open brackets must be closed by the same type of brackets.)

(문제의 주의사항을 더욱 유의깊게 보는 습관을 들여야겠다.)

 

어쨌든 '(())' 등 (,{,[ 왼쪽 괄호가 나올땐 모두 스택에 담는다. 그후 ),},]등 오른쪽괄호가 나올때부터 Stack에서 하나씩 꺼내어(pop) 해당 괄호의 짝인지 확인한다.이를 위하여 key:value hash를 이용한다. 마지막으로 모두 짝이맞아 스택이 비었다면 True를 리턴해준다.

 

각 괄호에 알맞는 짝이 나오게하는 문제이니, stack임을 알아차리는게 핵심이었다.

내가푼건 지저분하기에 leetcode베스트코드를 올린다.

---

SOLUTION CODE

# PYTHON Best Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = { ")" : "(", "]":"[", "}":"{"}

        for c in s:
            if c in closeToOpen: # 해당 키 값이 있나 확인 ),],} 
                if stack and stack[-1] == closeToOpen[c]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)
        return True if not stack else False

 

# C++ Best Code

class Solution {
public:
    bool isValid(string s) {
        string st;
        map<char,char>mp; // 괄호 짝 맵핑
        mp['('] = ')';
        mp['{'] = '}';
        mp['['] = ']';
        st.push_back(s[0]);
        for (int i = 1; i < s.size(); i++) {
            if(mp[st.back()] == s[i]) //괄호짝이맞다면
                st.pop_back(); //pop
            else
                st.push_back(s[i]);
        }
        return st.size() ? 0 : 1;
    }
};