LeetCode - 20. Valid Parentheses

유명한 문제로 stack 사용해서 풀면 된다.

여는 괄호가 나올 때는 다 stack에 넣고 닫는 괄호가 나왔을 때는 stack의 top과 매칭되면 stack pop을 하고 매칭되지 않으면 false를 반환한다.

class Solution {
public:
    bool isValid(string s) {        
        stack<char> valid_brackets;

        for (auto i: s) {
            if (i == '(' || i == '[' || i == '{')
                valid_brackets.push(i);
            else {
                if (valid_brackets.empty())
                    return false;
                if ((i == ')' && valid_brackets.top() == '(') || 
                (i == '}' && valid_brackets.top() == '{') ||
                (i == ']' && valid_brackets.top() == '[') ){
                    valid_brackets.pop();
                } else {
                    return false;
                }

            }
        }
        if (!valid_brackets.empty())
            return false;
        return true;


    }
};

이렇게 했을 때는 3초로 좀 오래 걸렸다.

 

고민한 결과 unordered_map을 사용하고, 주어진 string 길이가 홀수일 때는 확인 과정 없이 바로 false를 반환하도록 했다.

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> brackets;
        brackets[')'] = '(';
        brackets['}'] = '{';
        brackets[']'] = '[';
        stack<char> valid_brackets;

        if (s.size() % 2 == 1)
            return false;

        for (auto i: s) {
            if (i == '(' || i == '[' || i == '{')
                valid_brackets.push(i);
            else {
                if (valid_brackets.empty())
                    return false;
                if (valid_brackets.top() == brackets[i]){
                    valid_brackets.pop();
                } else {
                    return false;
                }

            }
        }
        if (!valid_brackets.empty())
            return false;
        return true;


    }
};