[leetcode] 20. Valid Parentheses

문제

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

 

풀이

Valid Parenthese를 판별하는 문제는 스택(Stack) 자료구조를 사용하는 문제로 유명하다.

문자열을 순서대로 돌면서 여는 괄호가 나오면 죄다 스택에 넣는다.

닫는 괄호가 나오면 스택에서 가장 위의 원소와 현재 닫는 괄호가 매칭이 되는 지를 체크한다.

만약 이때, 스택이 비어있거나 매칭이 되지 않으면 Invalid하므로 바로 false를 return한다.

마지막으로 문자열을 다 계산한 후에, 스택이 비어있으면 올바른 괄호열이 된다.

 

Time Complexity : $O(n)$

 

코드

class Solution {
public:
    bool isValid(string s) {
        stack<char> S;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
            {
                S.push(s[i]);
                continue;
            }
            if(S.empty())return false;
            if(s[i]==')' && S.top()!='(') return false;
            if(s[i]==']' && S.top()!='[') return false;
            if(s[i]=='}' && S.top()!='{') return false;
            S.pop();
        }
        return S.empty();
    }
};