[leetcode 20] Valid Parentheses

Given a string s 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.

 

Example 1:

Input: s = "()" Output: true

Example 2:

Input: s = "()[]{}" Output: true

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

Input: s = "{[]}" Output: true

 

풀이:

스택을 사용하면 쉬운 문제

class Solution {
public:
    bool isValid(string s) {
        
        stack<char> stk;
        map<char, int> m;
        m['('] = 1;
        m[')'] = 1;
        m['['] = 2;
        m[']'] = 2;
        m['{'] = 3;
        m['}'] = 3;
        
        for(int i=0; i<s.length(); i++){
            
            if(s[i]=='(' || s[i]=='{' || s[i] =='['){
                stk.push(s[i]);
                continue;
            }
            
            if(stk.empty()){
                return false;
            }
            
            if(m[stk.top()] != m[s[i]]){
                return false;
            }
            
            stk.pop();
        }
        
        if(!stk.empty()){
            return false;
        }
        return true;
    }
};